How does a Java HashMap handle different objects with the same hash code?

by

A hashmap works like this (this is a little bit simplified, but it illustrates the basic mechanism):

It has a number of “buckets” which it uses to store key-value pairs in. Each bucket has a unique number – that’s what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).

When you lookup a value in the hashmap, by giving it a key, it will first look at the hash code of the key that you gave. The hashmap will then look into the corresponding bucket, and then it will compare the key that you gave with the keys of all pairs in the bucket, by comparing them with equals().

Now you can see how this is very efficient for looking up key-value pairs in a map: by the hash code of the key the hashmap immediately knows in which bucket to look, so that it only has to test against what’s in that bucket.

Looking at the above mechanism, you can also see what requirements are necessary on the hashCode() and equals() methods of keys:

  • If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it’s going to look in the same bucket).

  • If two keys are different, then it doesn’t matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.

More Related Contents:

  1. Understanding the workings of equals and hashCode in a HashMap
  2. How does Java order items in a HashMap or a HashTable?
  3. What exactly is bucket in hashmap?
  4. How to create a HashMap with two keys (Key-Pair, Value)?
  5. Get ArrayList entry of a HashMap Entry [closed]
  6. What are the differences between a HashMap and a Hashtable in Java?
  7. How can I generate an MD5 hash in Java?
  8. How to sort a HashMap in Java [duplicate]
  9. Sorting HashMap by values [duplicate]
  10. Is a Java hashmap search really O(1)?
  11. What is the use of hashCode in Java?
  12. What happens when a duplicate key is put into a HashMap?
  13. How is hashCode() calculated in Java
  14. How to update a value, given a key in a hashmap?
  15. What is the significance of load factor in HashMap?
  16. How can I combine two HashMap objects containing the same types?
  17. Sorting hashmap based on keys
  18. Find and replace words/lines in a file
  19. How to get the unique ID of an object which overrides hashCode()?
  20. Key existence check in HashMap
  21. What is the optimal capacity and load factor for a fixed-size HashMap?
  22. What is an “internal address” in Java?
  23. what is the difference between == operator and equals()? (with hashcode() ???)
  24. Why does HashMap require that the initial capacity be a power of two?
  25. What is a sensible prime for hashcode calculation?
  26. Java: how to convert HashMap to array
  27. Android – Get value from HashMap
  28. get string value from HashMap depending on key name
  29. Sorting the Map in descending order based on the value [duplicate]
  30. What is the Java equivalent of Objective-C’s NSDictionary?

Leave a Comment