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?

Answer 1

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.

Answer 2

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());
        }
    }

Answer 3

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.

Answer 4

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!!
        }
    }

Answer 5

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);
}