Difference between internal working of HashMap in JAVA 7 And JAVA 8

In both Java 7 and Java 8, the HashMap class is used to store key-value pairs. However, there are some differences in the internal working of HashMap between these two versions.

In Java 7, the internal structure of a HashMap consists of an array of linked lists, where each array index represents a bucket. The hash code of the key is used to determine the bucket where the key-value pair will be stored. If multiple key-value pairs map to the same bucket, they are stored as nodes in a linked list at that bucket. This mechanism is known as separate chaining.

Let's consider an example to illustrate this. Suppose we have a HashMap in Java 7 with four buckets and the following key-value pairs:

Key: "Apple" -> Value: "Red" Key: "Banana" -> Value: "Yellow" Key: "Grape" -> Value: "Purple"

The hash code of each key is computed, and based on that, the corresponding bucket is determined. In this example, let's assume that the hash codes are as follows:

The HashMap in Java 7 would internally look like this

Bucket 0: Bucket 1: Bucket 2: Bucket 3: ("Apple" -> "Red") -> ("Grape" -> "Purple") Bucket 4: Bucket 5: Bucket 6: Bucket 7: ("Banana" -> "Yellow")

When retrieving a value from the HashMap in Java 7, the hash code of the key is used to find the bucket. Then, the linked list at that bucket is traversed to find the matching key-value pair.

In Java 8, the HashMap class introduced a new mechanism called tree bins to handle situations where a bucket contains a large number of colliding entries. When a bucket exceeds a certain threshold, it converts into a balanced binary tree instead of using a linked list. This structure, known as a red-black tree, allows for more efficient searching and retrieval of key-value pairs.

Continuing with the previous example, if we add more key-value pairs to the HashMap

Key: "Lemon" -> Value: "Yellow" Key: "Orange" -> Value: "Orange" Key: "Cherry" -> Value: "Red"

The HashMap in Java 8 would internally look like this:

Bucket 0: Bucket 1: Bucket 2: Bucket 3: ("Apple" -> "Red") -> ("Grape" -> "Purple") Bucket 4: Bucket 5: Bucket 6: Bucket 7: ("Banana" -> "Yellow") Bucket 8: ("Cherry" -> "Red") -> ("Lemon" -> "Yellow") -> ("Orange" -> "Orange")

As you can see, the bucket that initially contained three key-value pairs ("Cherry", "Lemon", and "Orange") has been transformed into a red-black tree, making it more efficient to search for specific keys within that bucket.

When retrieving a value from the HashMap in Java 8, the hash code of the key is used to find the bucket. If the bucket is a linked list, the key-value pairs are compared using their hash codes and, if necessary, their actual values to find the match. If the bucket is a red-black tree, a binary search is performed