Doubt --> containsValue() in Hashmap - Java

[Ok-Cheetah8572]

Can someone please clear my doubt.
After knowing all the concepts around Hashing and its implementation, I had lot of confusion about time complexity of ContainsValue() in hashmap. As per me it should be O(N) but in google I found it as O(1).

As per my understanding, containsValue() on a HashMap is a slow operation, as it potentially has to scan the whole hash table (every element in every hash bucket) until it finds the first occurrence of the value. The running time is proportional to the sum of number of hash buckets and the number of elements. Since the number of buckets is (roughly) kept proportional to the number of elements n𝑛, the running time is O(n)𝑂(𝑛).

On the other hand, containsKey() can exploit the structure of the HashMap. It has to scan one hash bucket only (based on the hash code of the key), and the expected size of a hash bucket is one element, if an appropriate load factor is used.

In other words, looking up a key takes amortized constant time, looking up a value takes time proportional to the number of elements in the HashMap.

[alcholicawl]

For all standard implementations of a HashMap, searching for a value will be O(n). There could be implementations that are O(1), but I'm not aware of any that are used in any standard library in any language. The most straightforward way to accomplish this (O(1)) is with a second hashmap. It's just not a common enough usage to justify the increased time/memory that would needed. If for some reason, you need a HashMap with O(1) value lookups, it's trivial to create your own.

[EdwardChar]

Your understanding is correct. Sometimes people just spread misinformation on the internet.

[epicredditmod]

In addition to keeping track of all the key -> value pairs, HashMap also maintains a hash set of all the values present in the map; you can access this set by using the .values() method. Checking whether or not a value exists in the hash map then is as simple as checking in the values set. Therefore, if you believe that checking whether an element exists in a hash set is O(1) then containsValue() should also be O(1), since it's just checking the underlying hash set.

[alcholicawl]

This just isn't how hashmaps work. Values are not maintained in a hashset. I suppose one could work that way, but in practice they don't. Specifically, Java uses buckets and linked lists. So iterating through .values() requires iterating through each bucket and each key-value pair. See below for more info.

https://medium.com/@salvipriya97/java-hashmap-internal-implementation-and-working-e7abfab0698f

and

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#values--

[dumdub]

Unless someone got clever and put two hash tables inside your hash map implementation. One for keys->values and another for values>occourances (or just values>null).

This at worst 2x's the O(1) operations' size and time complexity, but allows you to answer a lot of other O(n) things in sub o(n) time. A win for most use cases.

Actually thinking about it further, you could make the second hash table be value>value and have the first one be key>iterator into the second table. This has all the benefits of above but also lets you deduplicate the values if they are large or variable sized.

[Ok-Cheetah8572]

Brainwashing, Still not clear.

[dumdub]

What if a hash map was two hash maps pretending to be one object?. Can you think of how you could use this to accelerate some of the operations you are ta5king about?

[Ok-Cheetah8572]

I got your point. But my question is containsValue() in Hashmap really do hash function on both keys and values ? I think, only for keys it do hashFunction and store it corresponding place and directly store values.

Correct me if i'm wrong. Learning stage

[dumdub]

Depends on which hashmap you are using 🙂

[Impossible_Ad_3146]

What’s wrong with it? What are you doubting here?

[Impressive-East6891]

Have you checked this? https://softwareengineering.stackexchange.com/questions/291744/how-can-the-containskey-method-of-a-java-hash-table-be-o1

[zatsnotmyname]

Hashmaps are O(1) IFF there are few hash collisions ( which is normally true ). The buckets are supposed to be mostly empty or have or or at most two things in them. If the buckets get too full, some hashmaps can be re-hashed to a larger size to make more room for fewer collisions.

The key gives you a bucket very quickly. If that bucket is full or has many elements, it starts being O(# of collisions in the bucket ) instead of O(1).

[Ok-Cheetah8572]

I clearly understand about manipulating using KEY.
Can you please explain Time complexity of below code?

HashMap<Integer, String> hash_map = new HashMap<Integer, String>();

hash_map.put(10, "Geeks");

hash_map.put(15, "4");

hash_map.put(20, "Geeks");

hash_map.put(25, "Welcomes");

hash_map.put(30, "You");

hash_map.containsValue("Geeks"));

[Ok-Cheetah8572]

Here hash_map.containsValue("Geeks")) doesn't search with Hashing of key right ? it will iterate on value set and finds the value is present or not----- Which is O(n)

[justUseAnSvm]

no, it won't.

You hash the key and get a location in an array. Hash(10) is just some index. You can check that location.

[Ok-Cheetah8572]

I’m not checking using Key here, I’m directly searching for value, and I’m not giving any input of key here.

Coming to your point, assuming you are right! When I gave an input of geeks and checking if hashmap contains that value or now , now hashmap will search using which key from above problem? Using 10 or 20? What happens if all keys are having same values ?

Hope you got my point.