Java, quickest way to determine if any values in hashmap match a value?

Question

Pardon my newbie-ness to Java as I am not experienced enough to know the most efficient way to do this. I have a hashmap like below, but it would have like 40,000 entries:

Map <String, String> someHashmap = new HashMap <String, String> ();
someHashmap.put("filepath1", null);
someHashmap.put("filepath2", "tag1");
someHashmap.put("filepath3", "tag2");

I want to determine how many value match null so that I can determine if any are null. Of course I could do a regular loop to check but am wondering if there is a more efficient way, thanks

Answer 1

You can use the containsValue method, which states:

Returns true if this map maps one or more keys to the specified value.

somHashmap.containsValue(null);

However keep in mind, that if you have a large dataset(and it seems you do), you should create a separate data structure to keep track of the values that allow for O(1) lookup time, rather than O(n) time, as suggested in other answers.

Answer 2

Here's an alternative solution, designed for speed.

Call your original HashMap a. Have a second HashMap<String, Integer> aCount. The aCount hash map is going to store a count of how many of each value is in your original hash map.

Every time you insert a key k and value v into the first HashMap, check to see if aCount.containsKey(v). If it does, then increment the value: aCount.put(v, aCount.get(v) + 1). Otherwise, add a new entry: aCount.put(v, 1).

Every time you remove a key k and value v from the first HashMap, check the count using aCount.get(v). If the count is greater than one, then use aCount.put(v, aCount.get(v) - 1) to decrement the count. Otherwise (i.e. the count is exactly one) use aCount.remove(v).

Then, you need only call aCount.contains(v) to find out whether or not a given value is in your HashMap a.

Why do all this? Because, this way, instead of having an O(n) query time to find out if a value exists in your HashMap, you get O(1) time. If this is valuable to you, then the above solution will work. If this doesn't matter to you, then you can easily use Mike Lewis's answer.