How can I efficiently get all Strings from a HashMap that match a regex/prefix [Java]

I have a HashMap that has a bunch of string data read into it, I want people to be able to search for Strings by typing in a Search String, and the HashMap should give out all the data that matches that Search String.

for example:

Search String: Do

Results:

Dog

Dodo

Donkey

Doritos

Whats a way I can achieve this while keeping the time complexity good?

Solution

A TreeMap is a NavigableMap which is a SortedMap allows you to find the entry with the first key less than or equal to a given value, the next entry with a key after a given value, or even a sub-map with all the entries between a starting and an ending value.

If you're looking for all entries starting with "Do" the first entry that is not part of that set would end with "Dp" or some later value. In general, the first prefix that does not match can always be found by incrementing the last character of the prefix you are searching for. Here is how you can use this to solve your problem:

public void search(NavigableMap<String, String> navmap, String searchTerm) {
    String stopTerm = incrementLastChar(searchTerm);
    System.out.format("Searching range [%s, %s)%n", searchTerm, stopTerm);
    SortedMap<String, String> range = navmap.subMap(searchTerm, stopTerm);
    for (Map.Entry<String, String> entry : range.entrySet()) {
        System.out.println(entry.getKey());
    }
}

public String incrementLastChar(String term) {
    char[] chars = term.toCharArray();
    chars[chars.length - 1] += 1;
    return new String(chars);
}

Put the data you want to search in a TreeMap. I don't know what your values are, so I've simply made it a TreeMap from String to String. Pass it in as a NavigableMap along with the prefix you want to search for. I've created a helper method to create the stop term. That is, the lowest prefix that is not in the range you want to search. The search method prints out the range it is searching, and the keys of all the items found.