0

I searched many posts but I didnt find answer. I'd like to search and access values in collection by searching by value. My object type is DictionaryWord with two values: String word and int wordUsage (number of times the word was used). I was wondering which collection would be the fastest. If I write down "wa" I'd like it to give me e.g. 5 strings that start with these letters. Any list or set would be probably way too slow as I have 100 000 objects.

I thought about using a HashMap by making its key values String word and its values int wordUsage. I could even write my own hash() function to just give every key same value after hashing - key: "writing", hash value: "writing". Considering there are no duplicates would it be a good idea or should I look for something else?

My point is: how and what do I use to search for values that have some part of the value used in the search condition. For example writing down "tea" i find in collection values like: "tea", "teacher", "tear", "teaching" etc.

TheGame
  • 1
  • 4
  • 2
    you want to look into a trie: http://en.wikipedia.org/wiki/Trie – guido Jun 06 '15 at 12:47
  • Thank you kind Sir! That is exactly what I was looking for. Now into looking how to use it :) Thank you very much – TheGame Jun 06 '15 at 12:56
  • possible duplicate of [Java Hashmap: How to get key from value?](http://stackoverflow.com/questions/1383797/java-hashmap-how-to-get-key-from-value) – TheCodingFrog Jun 06 '15 at 12:59
  • I guess it is somehow connected but not exactly. Yes if I had to implement the Hashmap idea this would be somewhat useful. However the gist of the problem is completely different. It is not about searching and accessing the value. It is about searching for values that have a part of the value given in the search block. And by reading some examples I find Tries the best here. Though the implementation is a little bit complex. – TheGame Jun 06 '15 at 14:06
  • For the implementation, I'd suggest looking at the code/use the class from lucene: https://lucene.apache.org/core/4_0_0/analyzers-stempel/org/egothor/stemmer/Trie.html – guido Jun 07 '15 at 13:18

2 Answers2

0

The fastest I can think of is a binary search tree. I found this to be very helpful and it should make it clear why a tree is the best option.

Alexander
  • 480
  • 2
  • 5
  • 21
0

Probably, you need prefix tree. Take a look at Trie wiki page for further information.

Denis Borovikov
  • 737
  • 5
  • 9