Java Hashmap - Please explain how hash maps work

Question

I am currently preparing for interviews, Java in particular.

A common question is to explain hash maps.

Every explanation says that in case there is more than a single value per key, the values are being linked listed to the bucket.

Now, in HashMap class, when we use put(), and the key is already in the map, the value is not being linked to the existing one (at list as I understand) but replacing it:

Map<String, Integer> map = new HashMap();
map.put("a", 1);
//map now have the pair ["a", 1]
map.put("a", 2);
//map now have the pair ["a", 2]
//And according to all hash maps tutorials, it should have been like: ["a", 1->2]

From the docs:

If the map previously contained a mapping for the key, the old value is replaced.

What am I missing here? I am a little confused...

Thanks

Answer 1

You're confusing the behaviour of a Map with the implementation of a HashMap.

In a Map, there is only one value for a key -- if you put a new value for the same key, the old value will be replaced.

HashMaps are implemented using 'buckets' -- an array of cells of finite size, indexed by the hashCode of the key.

It's possible for two different keys to hash to the same bucket, a 'hash collision'. In case of a collision, one solution is to put the (key, value) pairs into a list, which is searched when getting a value from that bucket. This list is part of the internal implementation of the HashMap and is not visible to the user of the HashMap.

This is probably what you are thinking of.

Answer 2

Your basic understanding is correct: maps in general and hashmaps in particular only support one value per key. That value could be a list but that's something different. put("a", 2) will replace any value for key "a" that's already in the list.

So what are you missing?

Every explanation says that in case there is more than a single value per key, the values are being linked listed to the bucket.

Yes, that's basically the case (unless the list is replaced by a tree for efficiency reasons but let's ignore that here).

This is not about putting values for the same key into a list, however, but for the same bucket. Since keys could be mapped to the same bucket due to their hash code you'd need to handle that "collision".

Example:

Key "A" has a hash code of 65, key "P" has a hash code of 81 (assuming hashCode() just returns the ascii codes).

Let's assume our hashmap currently has 16 buckets. So when I put "A" into the map, which bucket does it go to? We calculate bucketIndex = hashCode % numBuckets (so 65 % 16) and we get the index 1 for the 2nd bucket.

Now we want to put "P" into the map. bucketIndex = hashCode % numBuckets also yields 1 (81 % 16) so the value for a different key goes to the same bucket at index 1.

To solve that a simple implementation is to use a linked list, i.e. the entry for "A" points to the next entry for "P" in the same bucket.

Any get("P") will then look for the bucket index first using the same calculation, so it gets 1. Then it iterates the list and calls equals() on each entry's key until it hits the one that matches (or none if none match).

Answer 3

in case there is more than a single value per key, the values are being linked listed to the bucket.

Maybe you mistake that with: Multiple keys can have the same hashCode value. (Collision)

For example let's consider 2 keys(key1, key2). Key1 references value1 and Key2 references value2.

If

hashcode(key1) = 1

hashcode(key2) = 1

Answer 4

The objects might have the same hashCode, but at the same time not be equal (a collision). In that situation both values will be put as List according to hashCode. Values will be retrieved by hashCode and than you'll get your value among that values by equals operation.