Fast Lookup of Java

Question

I currently have a String array that I need to search many times for an exact match. What would be the best data structure to use?

Example - String array with elements

cat
dog
squirrel
raccoon
aardvark

The java code receives searches for strings and iterates over the array:

1. Query for 'dogg' - returns nothing
2. Query for 'raccoon' - returns raccoon

My current code does the following:

for (String element : myList) {
      if (element.equals(searchTerm)) {
            return searchTerm;
      }
}

Is there a more efficient way to do this search? I thought about using a Map, but I couldn't think of a good value (the key would be the 'dog'/'cat'/etc....). Should I use the same value for the key and the value? Is there a better data structure to use?

Answer 1

Use a HashSet here for best lookup performance. Please, note that Set won't allow for any duplicates though. Using a Map doesn't make much sense here since you're only interested in searching for the keys i.e. you don't have anything associated with it.

Sample Code :

Set<String> animals = new HashSet<String>(
                          Arrays.asList("cat", "dog", "squirrel", "raccoon"));
if (animals.contains("dog")) {
    System.out.println("Yep, dog's here!"); // prints
}
if (!animals.contains("aardvark")) {
    System.out.println("Ah, aardvark's missing!"); // prints
}

Note, that a List also has a contains() method but it iterates over all its elements to check if an item exists pretty much having the same poor performance you want to avoid when using the for loop.

Answer 2

You can use a Trie data structure

Here is an implementation in guava trie . And a trie complexity to search is O(L) where L = stringToSearch.length();

Answer 3

You can use a Set instead of a Map (or, in case of a Map, just use any value for the key):

if (mySet.contains(element)) {
    return element;
} else {
    return null;
}

Answer 4

return myList.contains(searchTerm) ? searchTerm : null;