Mapping a set of strings to a specific key value

Question

Say I have 3 sets of string values:

fruit: apple, berry, banana

color: red, blue, orange

vehicle: car, plane, truck

I'm looking for the most efficient way with Java to retrieve the parent value for each set such as:

getParentValue("banana") ---> fruit

Solution 1:

create a bunch of if/else statements or switch case:

if (fruitSet.contains(elem)) {
   return "fruit";
}
else if (colorSet.contains(elem)) {
   return "color";
} ...

This yields an O(n) lookup, n being numbers of sets.

Solution 2:

Create a hashmap which stores every child to parent value,

Key/Value:

apple/fruit
berry/fruit
banana/fruit
red/color
blue/color
orange/color
...

This yields an O(1) lookup time, but generates a large hash map as it stores every key - for some reason this solution feels ugly.

I am looking for some opinions or other approaches which might be more elegant.

Number of keys in your hash map will be equal to the number of elements in all the sets combined (from solution 1) — Ankur Shanbhag, Mar 11 '17 at 05:32

score 1 · Answer 1 · answered Mar 11 '17 at 06:02

Here is some code that only has 3 entries in the Map.

public static void main(String[] args) {
    Map<String, List<String>> myMap = new HashMap<>();
    myMap.put("fruit", new ArrayList<String>(Arrays.asList("apple","berry","banana")));
    myMap.put("color", new ArrayList<String>(Arrays.asList("red","blue","orange")));
    myMap.put("vehicle", new ArrayList<String>(Arrays.asList("car","plane","truck")));
    System.out.println(getKey(myMap, "blue"));
}

public static String getKey(Map<String, List<String>> map, String value) {
    for (String key : (Set<String>)map.keySet()) {
        List<String> list = map.get(key);
        if (list.contains(value)) {
            return key;
        }
    }
    return null;
}

score 1 · Accepted Answer · answered Mar 11 '17 at 06:28

The best approach is definitely your solution #2: if you want to be able to look up the category given a member, then the most efficient way is to have a Map from the member to the category. That's exactly what Map is for.

(Note that regardless of your approach, you'll have to store all the members. Storing them as keys is no uglier than storing them in some less-efficient way.)

score 0 · Answer 3 · answered Mar 11 '17 at 05:32

0

Hashmap idea is quite good but if you wanna further improve, you can set each object to an integer and store it in an array. This would be nice if you have some categories with very long name.

For example,

something1/very very long string
something2/very very long string

After the conversion:

apple/0
berry/0
banana/0
red/1
blue/1
orange/1
...
something1/i
something2/i

And your array will be:

arr = {"fruit", "color", ....., "very very long string", ....};

Unless you have so many entries( tens or millions) in your list with very long strings categories, it won't worth.

For example, your average string size is 16 chars and you have a million different rows, it means only 16 MB which is nothing for a modern computer, and you save only 12MB as an integer is 4B.

answered Mar 11 '17 at 05:32

smttsp

4,011
3
33
62

This is not a good idea. Strings are a reference type in Java, so if you want to avoid storing many copies of `"very very long string"`, you can easily solve that by storing many references to the same String instance. There's no reason to resort to your own reference table; in addition to complicating the code unnecessarily, it actually *increases* the amount of memory required. – ruakh Mar 11 '17 at 05:39
@ruakh, How will you do that? Like `String s1 = "very very long string"` and `something1 / s1` in the hashmap. – smttsp Mar 11 '17 at 05:46
It depends how you're building the map. For example, if the values are all hardcoded, then [string interning](http://stackoverflow.com/questions/10578984/what-is-string-interning) will happen automatically. But regardless of how you're building the map, it's never difficult to reuse string instances if that's important. In no case is it easier to store array indices instead. – ruakh Mar 11 '17 at 06:32

Mapping a set of strings to a specific key value

3 Answers3