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

Question

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.

Your third assertion is incorrect.

It's perfectly legal for two unequal objects to have the same hash code. It's used by HashMap as a "first pass filter" so that the map can quickly find possible entries with the specified key. The keys with the same hash code are then tested for equality with the specified key.

You wouldn't want a requirement that two unequal objects couldn't have the same hash code, as otherwise that would limit you to 2³² possible objects. (It would also mean that different types couldn't even use an object's fields to generate hash codes, as other classes could generate the same hash.)

HashMap is an array of Entry objects.

Consider HashMap as just an array of objects.

Have a look at what this Object is:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Each Entry object represents a key-value pair. The field next refers to another Entry object if a bucket has more than one Entry.

Sometimes it might happen that hash codes for 2 different objects are the same. In this case, two objects will be saved in one bucket and will be presented as a linked list. The entry point is the more recently added object. This object refers to another object with the next field and so on. The last entry refers to null.

When you create a HashMap with the default constructor

HashMap hashMap = new HashMap();

The array is created with size 16 and default 0.75 load balance.

Adding a new key-value pair

1. Calculate hashcode for the key
2. Calculate position hash % (arrayLength-1) where element should be placed (bucket number)
3. If you try to add a value with a key which has already been saved in HashMap, then value gets overwritten.
4. Otherwise element is added to the bucket.

If the bucket already has at least one element, a new one gets added and placed in the first position of the bucket. Its next field refers to the old element.

Deletion

1. Calculate hashcode for the given key
2. Calculate bucket number hash % (arrayLength-1)
3. Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find the correct Entry. If a desired element is not found, return null

You can find excellent information at http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

To Summarize:

HashMap works on the principle of hashing

put(key, value): HashMap stores both key and value object as Map.Entry. Hashmap applies hashcode(key) to get the bucket. if there is collision ,HashMap uses LinkedList to store object.

get(key): HashMap uses Key Object's hashcode to find out bucket location and then call keys.equals() method to identify correct node in LinkedList and return associated value object for that key in Java HashMap.

Here is a rough description of HashMap's mechanism, for Java 8 version, (it might be slightly different from Java 6).

---

Data structures

• Hash table
  Hash value is calculated via hash() on key, and it decide which bucket of the hashtable to use for a given key.
• Linked list (singly)
  When count of elements in a bucket is small, a singly linked list is used.
• Red-Black tree
  When count of elements in a bucket is large, a red-black tree is used.

---

Classes (internal)

• Map.Entry
  Represent a single entity in map, the key/value entity.

• HashMap.Node
  Linked list version of node.

  It could represent:

  • A hash bucket.
    Because it has a hash property.
  • A node in singly linked list, (thus also head of linkedlist).
• HashMap.TreeNode
  Tree version of node.

---

Fields (internal)

• Node[] table
  The bucket table, (head of the linked lists).
  If a bucket don't contains elements, then it's null, thus only take space of a reference.
• Set<Map.Entry> entrySet Set of entities.
• int size
  Number of entities.
• float loadFactor
  Indicate how full the hash table is allowed, before resizing.
• int threshold
  The next size at which to resize.
  Formula: threshold = capacity * loadFactor

---

Methods (internal)

• int hash(key)
  Calculate hash by key.

• How to map hash to bucket?
  Use following logic:

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }
  

---

About capacity

In hash table, capacity means the bucket count, it could be get from table.length.
Also could be calculated via threshold and loadFactor, thus no need to be defined as a class field.

Could get the effective capacity via: capacity()

---

Operations

• Find entity by key.
  First find the bucket by hash value, then loop linked list or search sorted tree.
• Add entity with key.
  First find the bucket according to hash value of key.
  Then try find the value:
  • If found, replace the value.
  • Otherwise, add a new node at beginning of linked list, or insert into sorted tree.
• Resize
  When threshold reached, will double hashtable's capacity(table.length), then perform a re-hash on all elements to rebuild the table.
  This could be an expensive operation.

---

Performance

• get & put
  Time complexity is O(1), because:
  • Bucket is accessed via array index, thus O(1).
  • Linked list in each bucket is of small length, thus could view as O(1).
  • Tree size is also limited, because will extend capacity & re-hash when element count increase, so could view it as O(1), not O(log N).

The hashcode determines which bucket for the hashmap to check. If there is more than one object in the bucket then a linear search is done to find which item in the bucket equals the desired item (using the equals()) method.

In other words, if you have a perfect hashcode then hashmap access is constant, you will never have to iterate through a bucket (technically you would also have to have MAX_INT buckets, the Java implementation may share a few hash codes in the same bucket to cut down on space requirements). If you have the worst hashcode (always returns the same number) then your hashmap access becomes linear since you have to search through every item in the map (they're all in the same bucket) to get what you want.

Most of the time a well written hashcode isn't perfect but is unique enough to give you more or less constant access.

You're mistaken on point three. Two entries can have the same hash code but not be equal. Take a look at the implementation of HashMap.get from the OpenJdk. You can see that it checks that the hashes are equal and the keys are equal. Were point three true, then it would be unnecessary to check that the keys are equal. The hash code is compared before the key because the former is a more efficient comparison.

If you're interested in learning a little more about this, take a look at the Wikipedia article on Open Addressing collision resolution, which I believe is the mechanism that the OpenJdk implementation uses. That mechanism is subtly different than the "bucket" approach one of the other answers mentions.