Java HashMap Internal Implementation and How It Works

HashMap in Java is a data structure that stores key-value pairs. It is part of the Java Collections Framework and provides constant-time performance O(1) for basic operations like get() and put(), assuming a good hash function.

1. Data Structure Used in HashMap

Internally, a HashMap is implemented as an array of buckets.
Each bucket is a linked list (before Java 8) or a balanced tree (red-black tree) (from Java 8 onwards, if collisions become too many).

Node Structure

Each node stores:

• hash → the hash code of the key
• key → the key object
• value → the associated value
• next → reference to the next node in case of a collision

static class Node < K,V > implements Map.Entry < K,V > {
  final int hash;    // hash code of the key
  final K key;       // key object
  V value;           // value associated with the key
  Node < K,V > next; // link to the next node (for collisions)
  Node(int hash, K key, V value, Node < K, V > next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }
}

So, at a high level:

• The array holds buckets.
• Each bucket is either empty or holds a chain/tree of nodes.
• Each node stores the mapping (key → value) along with links for collision handling.

🔹3. Hashing in HashMap

Hashing is the process of converting an object into an integer using the hashCode() method.

• hashCode() determines the bucket location where the key-value pair will be stored.
• If two keys have the same hash code, they may go into the same bucket (collision).
• To differentiate keys in the same bucket, HashMap also uses the equals() method.

Example – Custom Key Class

Suppose we want to store Employee details in a HashMap, where each Employee ID uniquely identifies the employee.

// EmployeeKey class used as HashMap key
class EmployeeKey {
    private int empId;
    private String department;

    EmployeeKey(int empId, String department) {
        this.empId = empId;
        this.department = department;
    }

    // Override hashCode for bucket calculation
    @Override
    public int hashCode() {
        // A robust hash: combine empId and department
        return 31 * empId + (department != null ? department.hashCode() : 0);
    }

    // Override equals to ensure key uniqueness
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        EmployeeKey other = (EmployeeKey) obj;
        return empId == other.empId &&
               (department != null && department.equals(other.department));
    }
}

Usage in HashMap

import java.util.HashMap;

public class EmployeeDemo {
    public static void main(String[] args) {
        // Create EmployeeKey-based HashMap
        HashMap<EmployeeKey, String> empMap = new HashMap<>();

        // Insert employee data
        empMap.put(new EmployeeKey(101, "HR"), "Alice");
        empMap.put(new EmployeeKey(102, "IT"), "Bob");
        empMap.put(new EmployeeKey(103, "Finance"), "Charlie");

        // Retrieve employee using same key
        System.out.println("Employee 101 in HR: " +
            empMap.get(new EmployeeKey(101, "HR")));

        // Try another department with same ID (different key)
        System.out.println("Employee 101 in IT: " +
            empMap.get(new EmployeeKey(101, "IT"))); // null
    }
}

Output

Employee 101 in HR: Alice
Employee 101 in IT: null

• ✔ Why this is better?
• Shows how hashCode() and equals() must be implemented for correct key comparison.
• Demonstrates different objects with same ID but different department being treated as different keys.

🔹3.a. hashCode() in Java

• Defined in Object class → public native int hashCode();
• The hashCode() method returns an integer value (hash code) for an object.
• By default (from Object class), it gives a number based on the memory reference of the object.
• You can override hashCode() in your class to provide your own logic (usually based on object fields).
• In HashMap, HashSet, and other hash-based collections, hashCode() is used to decide which bucket (index) an object will be stored in.

The syntax of the hashCode() method in Java looks like this:

@Override
public int hashCode() {
    // Implementation to calculate and return the hash code
}

When we insert a key-value pair, HashMap does not directly use the hashCode() value as the array index. Instead, it applies a supplemental hash function and then calculates the index using the formula:

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

where n is the capacity (default = 16).

Example

class Student {
    int id;
    String name;

    @Override
    public int hashCode() {
        return id; // simple implementation using 'id'
    }
}

Here, the student’s id is used to generate the hash code. So two students with the same id will go into the same bucket.

✅ In short:
hashCode() gives an integer for every object. Hash-based collections (like HashMap) use it to find the storage location (bucket).

🔹3.b. equals() Method in Java

• The equals() method is used to check if two objects are logically equal.
• It is defined in the Object class, so every class in Java inherits it.
• By default, Object.equals() compares memory references (i.e., checks if both references point to the same object).

👉 But in real-world applications, we often care about the content of objects, not just memory references. That’s why we override equals().

✅ Syntax

@Override
public boolean equals(Object obj) {
    // Implementation to compare the current object with another object
}

➤ Example Without Overriding

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

public class TestEquals {
    public static void main(String[] args) {
        Student s1 = new Student(1, "Ashish");
        Student s2 = new Student(1, "Ashish");

        System.out.println(s1.equals(s2)); // false ❌ (different memory locations)
    }
}

👉 Even though both students have the same data, equals() returns false because the default Object.equals() checks references.

➤ Example With Overriding

import java.util.Objects;

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;              // same reference
        if (!(obj instanceof Student)) return false; // type check

        Student other = (Student) obj;             // cast
        return id == other.id && Objects.equals(name, other.name);
    }
}

public class TestEquals {
    public static void main(String[] args) {
        Student s1 = new Student(1, "Ashish");
        Student s2 = new Student(1, "Ashish");

        System.out.println(s1.equals(s2)); // true ✅ (same content)
    }
}

👉 Now equals() checks values (id and name) instead of memory.
So two students with the same data are considered equal.

3.c. Default implementation and System.identityHashCode()

• Object.hashCode()’s default implementation typically returns a value derived from the object identity (often related to the memory address or an internal identity hash). The exact mechanism is JVM-dependent.
• System.identityHashCode(obj) returns the identity hash code one would get from Object even if the class overrides hashCode().

✍️ default identity hash codes are usually stable for the lifetime of the object within a single JVM run, but should not be treated as persistent identifiers across runs.

🔹4. How HashMap Uses equals()

1. When you put a key in HashMap, first it calls hashCode() to find the bucket.
2. If multiple keys go into the same bucket (collision), HashMap then uses equals() to compare the keys.
3. If equals() returns true, it treats them as the same key and replaces the value.

* Example with HashMap

import java.util.*;

class Employee {
    int id;
    String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Employee)) return false;

        Employee other = (Employee) obj;
        return id == other.id && Objects.equals(name, other.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name); // must override with equals()
    }
}

public class HashMapExample {
    public static void main(String[] args) {
        Map<Employee, String> map = new HashMap<>();

        Employee e1 = new Employee(101, "John");
        Employee e2 = new Employee(101, "John");

        map.put(e1, "Developer");
        map.put(e2, "Manager");

        System.out.println(map.size()); // 1 ✅ (same key because equals() is true)
        System.out.println(map.get(e1)); // Manager
    }
}

Output :

1
Manager

🔹5. Buckets, Load Factor, and Capacity in Detail

1. Bucket
   • A bucket is an element inside the internal array of a HashMap.Each bucket stores key-value pairs (as Node objects).If two different keys generate the same index (collision), they are stored in the same bucket using a Linked List or Balanced Tree (after Java 8, if collisions exceed a threshold).
   👉 Example: If both "Ashish" and "Aryan" hash to index 5, both entries are stored in bucket 5.
2. Capacity
   • The capacity of a HashMap means the total number of buckets available.
   • The default capacity is 16.
   • When you create a new HashMap without specifying size:
     • • HashMap<String, String> map = new HashMap<>();
   • Internally, it creates an array of 16 buckets.
   • 👉 Capacity decides how many buckets are available to store key-value pairs.

3. Load Factor
   • The load factor is a measure of how full the HashMap can get before it needs to resize.
   • Default load factor = 0.75 (75%).
   • Formula:
     • threshold = capacity * load factor
   • Example: If capacity = 16 and load factor = 0.75, then threshold = 16 * 0.75 = 12.
   • This means when the number of stored entries goes beyond 12, the HashMap will automatically rehash (resize).

4. Rehashing (Resize Process)
   • When the threshold is crossed, the capacity of the HashMap is doubled.
   • For example:
     • Initial capacity = 16, threshold = 12.
     • If we insert the 13th element, capacity becomes 32, and all existing key-value pairs are rehashed (re-distributed into new buckets).
   👉 Rehashing ensures that performance remains close to O(1) for get() and put() operations.

✅ Example to Understand

import java.util.HashMap;

public class HashMapBucketsExample {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();

        // inserting 13 elements (default threshold is 12)
        for (int i = 1; i <= 13; i++) {
            map.put(i, "Value " + i);
        }
    }
}

What happens internally:

• Capacity = 16, Load Factor = 0.75 → Threshold = 12.
• As soon as the 13th entry is inserted, rehashing happens.
• New Capacity = 32, New Threshold = 32 * 0.75 = 24.

🔹6. Internal Working of put() Method

1️⃣ Inserting First Key-Value Pair

map.put(new Key("apple"), 100);

Steps:

1. Calculate hash code of Key {"apple"} → assume 118.
2. Calculate index → 118 & (16-1) = Result: 6 (Convert Numbers to Binary and Apply Bitwise AND (&)
3. Create a Node object:
   • {
     int hash = 118
     Key key = {“apple”}
     Integer value = 100
     Node next = null
     }
4. Place this object at index 6 (since no other entry is present there).

✍️Note : To calculate the bucket index, first subtract 1 from the capacity (n-1), convert both the hash code and (n-1) to binary, and then apply the bitwise AND (&) operation. For example:

<strong>Index = 118 & (16 - 1) 
      = 118 & 15
      = 6</strong>

So, the key with hash code 118 will be stored in bucket index 6.”

2️⃣ Inserting Second Key-Value Pair

map.put(new Key("banana"), 200);

3️⃣ Inserting Third Key-Value Pair (Collision Example)

1. Bucket Selection → HashMap checks the bucket at that index.
   • If empty → insert new node.
   • If not empty (collision) → compare keys using equals().
     • If key already exists → replace value.
     • If different key → add new node to linked list / tree.
2. Treeification (Java 8+) → If a bucket contains more than 8 nodes, it is converted from linked list → red-black tree for faster lookup.

Collision Example

map.put(new Key("grapes"), 300);

Steps:

1. Calculate hash code of Key {"grapes"} → assume 118.
2. Calculate index → 118 & (16 - 1) = 6.
3. Create a Node object:
   • {
     int hash = 118
     Key key = {“grapes”}
     Integer value = 300
     Node next = null
     }

👉 Now, index 6 is already occupied by "apple".

• Check hashCode() and equals().
  • If both keys are the same → update the value.
  • Otherwise → link "grapes" node to "apple" node (using next reference).

So, at index 6, we now have a linked list:

👉 If another key with same hash is inserted → collision occurs → handled using LinkedList (JDK 7) or Balanced Tree (JDK 8+ if >8 entries).

✅Final HashMap buckets after these insertions:

• Index 3 → banana=200
• Index 6 → apple=100 → grapes=300

✍️Both apple and grapes will be stored in bucket[6]. If the keys are equal, the value is replaced; otherwise, they are linked together using the next reference.

HashMap Buckets After Insertions

Buckets (capacity = 16)

Index 0   : null
Index 1   : null
Index 2   : null
Index 3   : [banana=200]
Index 4   : null
Index 5   : null
Index 6   : [apple=100] -> [grapes=300]   (Collision handled via Linked List)
Index 7   : null
Index 8   : null
Index 9   : null
Index 10  : null
Index 11  : null
Index 12  : null
Index 13  : null
Index 14  : null
Index 15  : null

🔹6. Internal Working of get() Method

The get(K key) method is used to fetch the value associated with a given key.
If the key does not exist, null is returned.

Example 1: Fetch the data for key "banana"

map.get(new Key("banana"));

Steps:

1. Calculate hash code of key "banana" → assume 115.
2. Calculate index → 115 & (16 - 1) = 3.
3. Go to index 3 of the bucket array.
4. Compare the key using equals() at index 3 with "banana".
   • If match found → return value.✅

👉 Output: 200

Example 2: Fetch the data for key "grapes"

map.get(new Key("grapes"));

Steps:

1. Calculate hash code of key {"grapes"} → assume 118.
2. Calculate index → 118 & (16 - 1) = 6.
3. Go to index 6 of the bucket array.
   • First element at index 6 is "apple". Compare keys using equals() with "grapes".
   • Not equal ❌ → move to next node.
4. Second element at index 6 is "grapes". Compare with "grapes".
   • Match found ✅.
   • Return value → 300.

👉 Output: 300

✍️Note: The keys are compared using the equals() method. If a match is found, the corresponding value is returned; otherwise, the traversal continues to the next node until either a match is found or null is reached.

👉 Time Complexity:

• Best Case: O(1) (no collisions)
• Worst Case: O(log n) (tree structure in case of too many collisions)

🔹7. Performance Characteristics

• put() / get() → O(1) average, O(log n) worst-case (tree), O(n) worst (linked list with poor hash).
• resize() → Expensive, so choose an initial capacity if possible.
• Iteration → O(n), since all entries must be visited.

🔹8. Important Points

1. Keys must implement hashCode() and equals() properly.
2. HashMap allows one null key and multiple null values.
3. HashMap is not synchronized (use ConcurrentHashMap in multithreaded apps).
4. Iterators are fail-fast → they throw ConcurrentModificationException if structure changes during iteration.

For complete details and official documentation on Java HashMap, you can refer to the Oracle HashMap API