Efficient data structure that checks for the existence of a String

Question

I am writing a program that will add a growing number or unique rows to a data structure. Once this is done, I later need to constantly check for the presence of a string in it.

If I were to use an ArrayList, I believe that checking for any particular row will go through all the elements until the corresponding row is found (or reaches the end and returns false).

However, with HashMap, I know that in constant time I can just use the key as a String and return any non-zero object, making this operation faster. However, I'm not interested in populating a HashMap where the value is completely arbitrary. Is there a data structure available that uses hash functions but does not require value placement?

Answer 1

If I were to use an ArrayList, I believe that checking for any particular row will go through all the elements until the corresponding row is found

That's right, the list check for an element is linear in the number of entries in the list.

HashMap,

: Java HashSet<T>, HashMap .

, ;

Set<String> knownStrings = new HashSet<String>();
... // Fill the set with strings

if (knownString.contains(myString)) {
    ...
}

Answer 2

, , ( ?), , "/".

- trie radix; . , , . ( ). Java- ( , , ).

, , bloom filter; , ; " ". Java (, Guava ).

, a HashSet...

Answer 3

A HashSet is probably the correct answer, but if you choose (for simplicity, for example) to search for a list, it is probably more efficient to combine your words into String with delimiters:

String wordList = "$word1$word2$word3$word4$...";

Then create a search argument with your word between the delimiters:

String searchArg = "$" + searchWord + "$";

Then do a search, say contains:

bool wordFound = wordList.contains(searchArg);

Perhaps you can make this a bit more efficient by using StringBuilder to create a searchArg.