Check if a List is a value in a HashMap

Question

I want to check if a value exists.

My Code:

public static final Map<String, List<String>> m = new HashMap<>();

if(m.containsValue("gummi")) {...}

My problem is that the value is a List. How can I check for the List?

Solution 1

So I am going to interpret the question, as wanting to tell whether any value of the Map contains the target String.

There's probably a more appropriate third-party bi-direction multimap implementation. If you are reading this in the future such a type may be in Java SE - please edit this answer.

Given the data structures, this is going to require searching through the entire data. It may be better to have Map mapping the other way. Let's ignore that.

The streams one-liner expression solution:

m.values().stream().anyMatch(list -> list.contains("gummi"))

Edit: For Horse Voice, a non-stream version.

flatContains(m.values(), "gummi")

where

public static boolean flatContains(
    Iterable<? extends Collection<?>> collections,
    Object value
) {
    for (Collection<?> collection : collections) {
        if (collection.contains(value)) {
            return true;
        }
    }
    return false;
}

Often avoiding streams makes for more readable code (and faster). However, in this case, I would go straight for the streams. If flatMap was involved, the choice would be much closer.

Solution 2

Map<String, List<String>> m = new HashMap<>();

    List<String> list1 = new ArrayList<>();
    List<String> list2 = new ArrayList<>();
    List<String> list3 = new ArrayList<>();

    m.put("1", list1);
    m.put("2", list2);

    System.out.println(m.containsValue(list1));
    System.out.println(m.containsValue(list2));
    System.out.println(m.containsValue(list3));

Output

true
true
true

Explanation

As long as the new list is empty, the hashcode value is always 1. So list1,list2 and list3 will all have the hashcode value of 1. Basically meaning,

list1 = list2 = list3

So even if we check m.containsValue(list3); it will return true. But if the list is not empty, each list will have a unique hashcode. So as long as you have a map with non-empty lists then we could use containsValue(listObject) which will return correct result. Example below,

Map<String, List<String>> m = new HashMap<>();

    List<String> list1 = new ArrayList<>();
    List<String> list2 = new ArrayList<>();
    List<String> list3 = new ArrayList<>();

    list1.add("apple");
    list1.add("orange");

    list2.add("mobile");
    list2.add("computer");

    m.put("1", list1);
    m.put("2", list2);

    System.out.println(m.containsValue(list1));
    System.out.println(m.containsValue(list2));
    System.out.println(m.containsValue(list3));

Output:

true
true
false

Other use cases:

If we want to check whether the value in the map is of type list or we would like to check a value is present in one of the list, then we can iterate the map as below,

for (String key : m.keySet()) {
        if (m.get(key) instanceof List) {
            for (String listItem : m.get(key)) {
                if ("valueWeSearchFor".equalsIgnoreCase(listItem)) {
                    break;
                }
            }
        }else{
            //If the value in the map is not of type list
            //What to do!!
        }
    }

Solution 3

Java 7: contains for Map<String, List<String>>

Assuming the same as Tom, here is a Java 7 version (as requested by Horse Voice):

// Live version
static boolean contains(Map<String, List<String>> map, String value) {
    for (List<String> list : map.values()) {
        if(list.contains(value)) return true;
    }
    return false;
}

If your source Map doesn't change, it might be better to create a search cache:

// Cached version
private List<String> allValues = getInnerValues(map);
private List<String> getInnerValues(Map<String, List<String>> map) {
    List<String> result = new ArrayList<>();
    for (List<String> list : map.values()) {
        result.addAll(list);
    }
    return result;
}

static boolean contains(String value) {
    return allValues.contains(value);
}

Java 7: anyKeyForValue and keysForValue

I figure some people will want the key(s) that match the value:

// Live version
static String anyKeyForValue(Map<String, List<String>> map, String value) {
    for (Entry<String, List<String>> entry : map.entrySet()) {
        if(entry.getValue().contains(value)) return entry.getKey();
    }
    return null;
}

static List<String> keysForValue(Map<String, List<String>> map, String value) {
    List<String> result = new ArrayList<>();
    for (Entry<String, List<String>> entry : map.entrySet()) {
        if(entry.getValue().contains(value)) result.add(entry.getKey());
    }
    return result;
}

Caching is a little harder; we need to invert the Map:

// Cached version
private Map<String, List<String>> valueKeys = invert(map);
private Map<String, List<String>> invert(Map<String, List<String>> map) {
    Map<String, List<String>> result = new HashMap<>();
    for (Entry<String, List<String>> entry : map.entrySet()) {
        for (value : entry.getValue()) {
            List<String> keys;
            if (result.containsKey(value)) {
                keys = result.get(value);
            } else {
                keys = new ArrayList<String>();
                result.put(value, keys);
            }
            keys.add(entry.getKey());
        }
    }
    return result;
}

static List<String> keysForValue(String value) {
    return valueKeys.get(value);
}

Solution 4

I've checked two scenarios using java 8. The below analysis is for the worst-case scenario.

scenario 1: map contains 1000000 keys

It seems to be in this scenario, java stream API is slower than loops. the map contains 1000000 keys. the Streams took 107543400 nanoseconds to complete the task. Loops took 73688600 nanoseconds. however, The parallel stream only took 51464500 nanoseconds.

checkout the below solution code.

public static void main(String[] args) {
    try {
        App app = new App();
        String parameter = "invalid value";
        int numberOfKeys = 1000000;

        Map<String, List<String>> m = new HashMap<>();

        // adding values to map
        for (int i = 0; i < numberOfKeys ; i++) {
            m.put(i + "",
                    Arrays.asList(i * 10 + "", i * 11 + "", i * 12 + "", i * 13 + "", i * 14 + "", i * 15 + ""));
        }

        /** check time difference **/

        System.out.println("Loops");
        long begin = System.nanoTime();
        boolean b = app.containsValue_loops(m, parameter);
        System.out.println(System.nanoTime() - begin);
        System.out.println(b);

        System.out.println("\nJava 8 - stream");
        begin = System.nanoTime();
        boolean a = app.containsValue_java8(m, parameter);
        System.out.println(System.nanoTime() - begin);
        System.out.println(a);

        System.out.println("\nJava 8 - parallel stream");
        begin = System.nanoTime();
        boolean c = app.containsValue_java8_parallel(m, parameter);
        System.out.println(System.nanoTime() - begin);
        System.out.println(c);

    } catch (Exception e) {
        System.out.println(e);
    }
}


/** Checks parameter contains in the list using loops **/
public boolean containsValue_loops(Map<String, List<String>> m, String parameter) {
    for (List<String> list : m.values()) {
        if (list.contains(parameter)) {
            // return immediately if value contains in the list
            return true;
        }
    }
    return false;
}

/** Checks parameter contains in the list using streams **/
public boolean containsValue_java8(Map<String, List<String>> m, String parameter) {
    return m.values().stream().anyMatch(list -> list.contains(parameter));
}

/** Checks parameter contains in the list using parallel streams **/
public boolean containsValue_java8_parallel(Map<String, List<String>> m, String parameter) {
    return m.values().parallelStream().anyMatch(list -> list.contains(parameter));
}

This is the output :

Loops
73688600
false

Java 8 - stream
107543400
false

Java 8 - parallel stream
51464500
false

scenario 2: map contains only 10 keys

This is the output :

Loops
185000
false

Java 8 - stream
31721800
false

Java 8 - parallel stream
2987000
false

In this scenario, for loops take less time than streams. it is also faster than parallel streams.

So as the conclusion my suggestion is to use loops for a small collection, and use a parallel stream if you have a larger collection.

Solution 5

Iterate Map collection to check inputString with every map values so that you can use match found keys for further use.

    Map<String, List<String>> m = new HashMap<>();
    String searchStr="a";
    List<String> list1 = new ArrayList<>();
    list1.add("a");
    list1.add("b");
    m.put("1", list1);
    list1 = new ArrayList<>();
    list1.add("c");
    m.put("2", list1);
    list1 = new ArrayList<>();
    list1.add("a");
    list1.add("d");
    m.put("3", list1);

    for (Entry<String, List<String>> entry : m.entrySet()) {
        if (entry.getValue().contains(searchStr)) {
            System.out.println(searchStr+" found for map key="+entry.getKey());
        }
    }

View more solutions

Comments

[Jacob G.]

@HorseVoice What would you say that the OP is asking, exactly? It's still not clear to me. Are they asking if any List in the Map contains "gummi", or are they asking if there exists a List in the Map that only contains "gummi"? I'd be happy to write an answer that caters to both situations.

[George Simms]

This requires the caller to know all members of the list that is a value.

[Horse Voice]

@Tunaki, this is not what the questioner is asking.. If you already knew the contents of the array then this problem is trivial. Interesting problem to solve if you don't know what the contents of the list will contain. Your answer takes a shortcut and doesn't fully answer the question. I've set a bounty on this.

[Horse Voice]

can you give the same answer in java 7 not including lambdas?

[Surender Khairwa]

@HorseVoice: Added Java 7 version here: stackoverflow.com/a/58871387/2015408

[charles-allen]

If you're not going to cache, then you should definitely be short-circuiting when you find a match! You might find "gummi" in the first list!

[Brett]

I don't understand why you think the while loop is better. Not unless you were going for some kind of SESE (Single Entry Single Exit) style: while (iterator.hasNext() && (entry = iterator.next()).getValue().equals(gummi)) {. (Not a style I particularly like, but see where it is coming from, but not particularly helpful here.)

[Brett]

Um, I'm sure it works. It's only appropriate for situations where you are going to do many searches without updating the underlying data, which seems niche. If you want that mapping, probably keep it that way. Having said that, maintaining multiple copies of data in the presence of errors is troublesome. / In general the reverse mapping of Map<K, List<V>> will be Map<V, Collection<K>> not Map<V, K>. Collectors.groupingBy may or may not be useful Also, there is Map.entry from ye olde, not publicly maintained by Oracle, Java SE 9. (Not my -1, btw.)

[kakashi hatake]

@TomHawtin-tackline thanks to comment. I just though search and your comments absolutely true

[Naman]

Or perform a flatMap to avoid contains over a list, m.values().stream().flatMap(Collection::stream).anyMatch(str -> str.equals("gummi"))

[Brett]

@Naman You could, but I don't think there would be much advantage in this case. flatMap makes it less clear and, I think, the performance will be worse. It does, however, allow you to switch the predicate to something more interesting.

[Reodont]

In addition to previous comment. Don't use double-bracket initialization, we don`t need useless anonymous classes.

[Subhanshuja]

i think this code is right answer, have you tried this code @max

[Naman]

... and the reason to downvote is? (just a comment for the downvoter, not that I actually expect a reply :))