CODEWITHSUNDEEP
javaarraysstring
David
David

Reputation: 1107

Fast Lookup of Java

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?

Upvotes: 5

Views: 8922

Answers (7)

nachokk
nachokk

Reputation: 14413

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();

Upvotes: 4

Ruchira Gayan Ranaweera
Ruchira Gayan Ranaweera

Reputation: 35597

Try this

    String[] arr = new String[]{"cat", "dog", "squirrel", "raccoon", "aardvark"};
    List<String> list=new ArrayList<String>(Arrays.asList(arr));
    System.out.println(list.contains("dog") ? "found" : "not found");

Upvotes: 0

Ravi K Thapliyal
Ravi K Thapliyal

Reputation: 51721

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.

Upvotes: 12

Prasad Kharkar
Prasad Kharkar

Reputation: 13576

Put them in HashSet as it uses hashing which is a technique for fast retrieval of elements as it uses hashcode to store them. 

Sub obj = new Sub();
obj.items.add("one");
obj.items.add("two");
obj.items.add("three");

System.out.println(obj.items.contains("one"));

Upvotes: 0

JREN
JREN

Reputation: 3630

If you only want to return you search term, you can do it like this

String result = myList.contains(searchTerm) ? result : "";

Upvotes: 0

Philipp Sander
Philipp Sander

Reputation: 10249

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

Upvotes: 1

Joey
Joey

Reputation: 354874

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;
}

Upvotes: 1

Related Questions