Efficient way of searching String Array in Hashmap

Question

I have following hashmap with a string array:

public static HashMap<String, String[]> map = new HashMap<String, String[]>();
map.put("calculus",new String[] {"math","logic"});
map.put("chemisty",new String[] {"ions","electrons"});
map.put("biology",new String[] {"life","bacteria"});

I have a string which I want to search in the String arrays in the Hashmap. My code is:

public String findFn(String myString) {

    for (Map.Entry<String, String[]> entry : map.entrySet()) {

        String key = entry.getKey();

        for(String s : entry.getValue()) {
            if(s.contains(myString)) {
                return key;
            }
        }
    }
    return null;    
}

This would effectively iterate through entire hashmap values until the match is found. Is there any better way to do this?

Maybe maintain a reverse map with arrayElement -> key (if this search happens very often) — ernest_k
– ernest_k, Commented Apr 25, 2019 at 17:45
If you want efficient searching, a hashmap of plain arrays is a terrible choice. Then again, if this is all the data you have, the idea of needing efficient searching seems... irrelevant? Just maintain a parallel reverse lookup, which given your data looks like it can just be a string:string map. Then do your lookups in O(1) — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Apr 25, 2019 at 17:45
@Mike'Pomax'Kamermans I have thousands of records in the hashmap. Then what is the efficient data structure for this? A piece of code would help :) — user5155835
– user5155835, Commented Apr 25, 2019 at 17:47
What if the value is in multiple entries? I don't know what the data will be, but I guess that for example DNA could be in both chemistry and biology. — NeplatnyUdaj
– NeplatnyUdaj, Commented Apr 25, 2019 at 17:48

Code-Apprentice · Accepted Answer · 2019-04-25 17:44:45Z

3

With your current data structure, this is the best you can do. If you need to do this often, you should build another Hashmap with the reverse relationship where the "topic" is the key and the "course" is the value.

answered Apr 25, 2019 at 17:44

Code-Apprentice

84k26 gold badges162 silver badges289 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Code-Apprentice Over a year ago

@user5155835 map.put("math", "calculus");

NeplatnyUdaj · Accepted Answer · 2019-04-25 17:55:57Z

If the number of entries in the HashMap will be low and number of items in the values will be high, I would go with just a slight modification of your code replacing arrays with HashSets:

public static HashMap<String, Set<String>> map = new HashMap<>();
map.put("calculus", new HashSet());
map.get("calculus").add("math");
...

public String findFn(String myString) {
    for (Map.Entry<String, Set<String>> entry : map.entrySet()) {           
        for(String s : entry.getValue()) {
            if(s.contains(myString)) {
                return entry.getKey();
            }
        }
    }
    return null;
}

The HashSet.contains() has constant-time performance so the code will iterate only on the number of classifiers.

Collectives™ on Stack Overflow

Efficient way of searching String Array in Hashmap

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related