Understanding HashMap's Internal Workings in Java

Introduction

Ever wondered how Java's HashMap efficiently stores and retrieves data? Let's break down its internal structure, keeping it simple and relatable.

How Does It Work Internally?

1. Hashing

Java converts a key into a number (hash code). For example, "Apple" might become 12345.

2. Buckets

The HashMap has an array of buckets (boxes), each holding a key-value pair. The hash code decides which bucket to use.

3. Collisions

If two keys have the same hash code, they go into the same bucket using a linked list.

Example

1Map<String, String> map = new HashMap<>();
2map.put("name", "John");
3System.out.println(map.get("name")); // Outputs: John

Internal Steps Explained

Put Operation:

Convert the key to a hash code.

Find the correct bucket.

Store the key-value pair.

Get Operation:

Convert the key to a hash code.

Find the bucket.

Retrieve the value.

Resize Operation:

When full, create a bigger array.

Move all key-value pairs to new buckets.

Complete Code Implementation

1import java.util.Objects;
2
3public class CustomHashMap<K, V> {
4
5    static class Node<K, V> {
6        final int hash;
7        final K key;
8        V value;
9        Node<K, V> next;
10
11        Node(int hash, K key, V value, Node<K, V> next) {
12            this.hash = hash;
13            this.key = key;
14            this.value = value;
15            this.next = next;
16        }
17    }
18
19    private Node<K, V>[] table;
20    private int capacity = 16;
21    private int size = 0;
22
23    public CustomHashMap() {
24        table = new Node[capacity];
25    }
26
27    private int hash(Object key) {
28        return key == null ? 0 : Objects.hashCode(key) & (capacity - 1);
29    }
30
31    public void put(K key, V value) {
32        int index = hash(key);
33        Node<K, V> newNode = new Node<>(index, key, value, null);
34        if (table[index] == null) {
35            table[index] = newNode;
36        } else {
37            Node<K, V> current = table[index];
38            while (current.next != null || current.key.equals(key)) {
39                if (current.key.equals(key)) {
40                    current.value = value;
41                    return;
42                }
43                current = current.next;
44            }
45            current.next = newNode;
46        }
47        size++;
48    }
49
50    public V get(K key) {
51        int index = hash(key);
52        Node<K, V> current = table[index];
53        while (current != null) {
54            if (current.key.equals(key)) {
55                return current.value;
56            }
57            current = current.next;
58        }
59        return null;
60    }
61
62    public int size() {
63        return size;
64    }
65
66    public static void main(String[] args) {
67        CustomHashMap<String, String> map = new CustomHashMap<>();
68        map.put("name", "John");
69        System.out.println(map.get("name")); // Outputs: John
70    }
71}

Why Use HashMap?

Fast lookups.

Easy to use.

Handles large data efficiently.

This explanation simplifies how a HashMap works internally with a straightforward example. Perfect for beginners learning Java!