HashMap Implementation in Java

What is a HashMap?

A HashMap in Java is a part of the java.util package and implements the Map interface. It stores data in key-value pairs, allowing fast retrieval, insertion, and deletion of elements based on keys.

How Does HashMap Work Internally?

1. Data Structure

• Internally, a HashMap uses an array of buckets (also called bins).
• Each bucket is a linked list (or a balanced tree in Java 8+ for high-collision buckets).
• Each element in the bucket is a Node object containing a key, value, hash, and a reference to the next node.

2. Hashing

• When you put a key-value pair, the key’s hashCode() is computed.
• The hash is used to determine the bucket index:
  index = hash % array.length
• If two keys have the same hash index (collision), they are stored in the same bucket (as a linked list or tree).

3. Put Operation

• Compute the hash for the key.
• Find the bucket using the hash.
• If the bucket is empty, insert the new node.
• If not, check if the key already exists:
• If yes, update the value.
• If no, add the new node to the bucket (linked list or tree).

4. Get Operation

• Compute the hash for the key.
• Find the bucket using the hash.
• Traverse the bucket (linked list/tree) to find the node with the matching key.
• Return the value.

Get Saumya14’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

5. Resize (Rehashing)

• When the number of entries exceeds the load factor (default 0.75), the array size is doubled.
• All existing entries are rehashed and moved to the new array.

Representation

1. Buckets (Array) Representation

This shows the array of buckets in a HashMap, where some buckets are empty (null).

// Array of buckets (size 5 for illustration)
Node[] buckets = new Node[5];

2. Linked List in a Bucket (Collision Handling)

This shows how multiple entries in the same bucket are stored as a linked list due to hash collisions.

// Node class for HashMap
class Node {
    String key;
    int value;
    Node next;
    Node(String key, int value) {
        this.key = key;
        this.value = value;
    }
}

// Example of a linked list in a bucket
Node bucket2 = new Node("apple", 10);
bucket2.next = new Node("grape", 30);

3. HashMap with Multiple Buckets and Collisions

This shows a HashMap with several buckets, including one with a linked list due to collisions.

Node[] buckets = new Node[5];

// Bucket 2: 'apple' -> 'grape'
buckets[2] = new Node("apple", 10);
buckets[2].next = new Node("grape", 30);

// Bucket 4: 'banana'
buckets[4] = new Node("banana", 20);

4. Node Structure

This shows the structure of a single node in a HashMap bucket.

class Node {
    String key;
    int value;
    int hash;
    Node next;
    Node(String key, int value, int hash) {
        this.key = key;
        this.value = value;
        this.hash = hash;
    }
}

Summary

• The array of buckets is the main storage.
• Collisions are handled by linked lists (or trees in Java 8+).
• Each Node stores key, value, hash, and a reference to the next node.