Search code examples
javahashmaphash-collision

How collision between different HashMap objects is avoided?

I have found that HashMaps calculate hashes for performance optimization. They use hashCode() to split up Keys into different buckets, and equals() for further comparison within those buckets.

However, I could not find an explanation of how collision between different HashMap objects is averted.

Current understanding:

  1. Different objects can have the same hash.
  2. Thus different Map Keys can end up in the same bucket.
  3. Keys of different maps can also have the same hash.
  4. Thus Keys of independent map objects can also end up in the same bucket.

If assumptions 3 and 4 are correct, would not it be possible for different HashMaps overwrite each others Values by accident? Or retrieve a Value that belongs to a wrong Map?

How is this avoided?

e.g.

HashMap<MyKey, Value> map1 = new HashMap<>();

HashMap<MyKey, Value> map2 = new HashMap<>();

Can MyKey values of map1 and map2 end up in the same bucket?

Can map2 instead of its own values start retrieving values of map1?

Solution

  • Different HashMap objects don't share buckets.

    Your item #2 should be changed to "different map keys of the same HashMap can end up in the same bucket" and #4 is straight up wrong, as each HashMap has its own array of buckets to use that a totally independent of what any other HashMap does.