Internal Working of HashMap in Java

HashMap in Java is a widely used data structure, which allows key-value pairs to be stored and retrieved in constant time. In this article, we will look into how the get() and put() methods work internally, along with the process of hashing, fetching, and storing the key-value pairs.

The HashMap in Java contains an array of Node, where Node represents a class with four objects: hash, key, value, and next. The hashing process involves converting an object into an integer using the hashCode() method, which needs to be implemented properly for the HashMap to perform better.

Here's an example of a custom Key class that overrides the hashCode() method for different scenarios:

vbnet
class Key {
  String key;
  Key(String key) {
    this.key = key;
  }

  @Override
  public int hashCode() {
    return (int)key.charAt(0);
  }

  @Override
  public boolean equals(Object obj) {
    return key.equals((String)obj);
  }
}

In this example, the hashCode() method returns the ASCII value of the first character of the key, which means that the hash code will be the same whenever the first character of the key is the same. However, this is not the ideal approach to implement in a program.

HashMap allows null key, so the hash code of a null key is always 0. The hashCode() method is used to calculate the bucket and, therefore, calculate the index. The equals() method is used to compare two objects to determine whether they are equal or not.

A bucket is an element of the HashMap array that stores nodes, where two or more nodes can have the same bucket. In that case, a linked list structure is used to connect the nodes. The relationship between the bucket and capacity is:

capacity = number of buckets * load factor

A single bucket can have more than one node, depending on the hashCode() method. The better the hashCode() method is, the better the buckets will be utilized.

The index calculation in HashMap involves generating a hash code for the key, which may be too large to create an array. Therefore, we generate an index to minimize the array's size. The following operation is performed to calculate the index:

index = hashCode(key) & (n-1)

where n is the number of buckets or the size of the array.

Now let's understand the internal working of HashMap with examples. Consider an initially empty HashMap with a size of 16:

java
HashMap map = new HashMap();

We can insert a key-value pair into this HashMap using the put() method, as shown below:

go
map.put(new Key("vishal"), 20);

Here, the hash code of the Key "vishal" is calculated to be 118, and the index is 6. Then, a node object is created with the following properties:

java
{
  int hash = 118
  Key key = {"vishal"}
  Integer value = 20
  Node next = null
}

This object is placed at index 6 if no other object is present.

Similarly, another key-value pair can be inserted into the same HashMap:

go
map.put(new Key("sachin"), 30);

Here, the hash code of the Key "sachin" is 115, and the index is 3. A node object is created with the following properties:

java
{
  int hash = 115
  Key key = {"sachin"}
  Integer value = 30
  Node next = null
}

Continuing from the previous example, let's consider inserting another key-value pair:

go
map.put(new Key("john"), 50);

Steps:

1. Calculate the hash code of the key "john". It will be generated as 106.
2. Calculate the index by using the index method. It will be 2.
3. Create a node object as:

java
{
  int hash = 106
  Key key = {"john"}
  Integer value = 50
  Node next = null
}

4. Place this object at index 2, if no other object is presented there.
5. Since there is no node object present at index 2, the new node object is placed there.

java
empty_hasharray
       |
       v
[empty, empty, {106, "john", 50, null}, empty, empty, empty, {118, "vishal", 20, {118, "vaibhav", 40, null}}, {115, "sachin", 30, null}, empty, empty, empty, empty, empty, empty, empty, empty]

Now, let's consider retrieving the value for a given key from the HashMap.

vbnet
map.get(new Key("john"));

Steps:

1. Calculate the hash code of the key "john". It will be generated as 106.
2. Calculate the index by using the index method. It will be 2.
3. Traverse the linked list at index 2 until a node with a matching key is found. In this case, the first node in the linked list has a key of "john", so it is returned and its corresponding value of 50 is returned as well.

50

That's how the get method works internally in a HashMap. It calculates the hash code of the key, calculates the index, and then traverses the linked list until it finds the node with the matching key. If no node is found, it returns null.