Searching through Collections in Java

Question

I have a java properties file containing a key/value pair of country names and codes. I will load the contents of this file into a Collection like List or HashMap.

Then, I want users to be able to search for a country, e.g if they type 'Aus' in a textbox and click submit, then I want to search through the collection I have, containing a key/value pair of country codes/names (e.g AUS=>Australia), and return those countries which are found matching.

Is there any more efficient way of doing this, other than looping through the elements of the collection and using charAt()?

Answer 1

Short of indexing the collection via something like Lucene, then you'd have to manually check by looping through all of the elements. You could use startsWith as opposed to looping over the string:

String userText = ...
for (Map.Entry<String, String> entry : map) {
    boolean entryMatches = entry.getKey().startsWith(userText);
    ...

Or alternatively use regular expressions:

Pattern pattern = Pattern.compile(userText);

for (Map.Entry<String, String> entry : map) {
    boolean entryMatches = pattern.matcher(entry.getKey()).find();
    ...

Answer 2

Looping with String.contains() is the way unless you want to move in some heavy artillery like Lucene.

Answer 3

Since the list is small enough to load into memory, sort it and then do a binary search, using the static method java.util.Collections.binarySearch(). This returns an index, and works regardless of whether the exact string is in the list or not (although if it's not it returns a negative number, so be sure to check that). Then, starting from that index, just iterative forward to find all the strings with that prefix. As a nice side-effect, the resulting output will be in alphabetical order.

To make the whole thing case insensitive, remember to convert to lowercase when loading the list and of course convert the prefix to lowercase before searching.

Answer 4

If performance is important, you can use a TreeSet or TreeMap to hold the country names, and do the following can be used to identify countries that start with a given string.

NavigableMap<String, String> countries = new TreeMap<String, String>();
countries.put("australia", "Australia");
...

String userText = ...
String tmp = userText.toLower();
List<String> hits = new ArrayList<String>();
Map.Entry<String, String> entry = countries.ceilingEntry(tmp);
while (entry != null && entry.getKey().startsWith(tmp)) {
    hits.add(entry.getValue());
    entry = map.higherEntry(entry.getKey());
}
// hits now contains all country names starting with the value of `userText`, 
// ignoring differences in letter case.

This is O(logN) where N is the number of countries. By contrast a linear search of a collection is O(N)

Answer 5

Well, this is alright. I am trying to look for a string pattern in an ArrayList. For example ArrayList contains {"Abcde", "ghldedp", "klmnop"} and i my search string is "Abc" how can i use Collections.binarysearch() to do this for me?

Let me know if someone has an idea.