Reputation: 1107
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:
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
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
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
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
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
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
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