Leetcode 706 Design HashMap - How HashMap is Implemented in Java (Easy, O(n))

Leetcode 706: Design HashMap

Problem Summary – Leetcode 706: Design HashMap

You're asked to implement a basic HashMap data structure that supports:

• put(key, value) — insert/update a key-value pair.
• get(key) — retrieve the value by key; return -1 if not found.
• remove(key) — remove the key-value pair by key.

Without using any built-in HashMap or HashTable classes.

---

💡 Solution Overview

You implement the MyHashMap using:

1. An array of buckets (ListNode[] map) where each bucket stores a linked list of nodes.
2. A fixed size of 1000 buckets.
3. A hash function: key % size to map a key to a bucket.
4. Separate chaining for collision resolution using singly linked lists.
5. A dummy head node for each bucket to simplify insertion and deletion logic.

---

🧩 How It Works

Hash Function:

int hash(int key) {
    return key % size;
}

This maps a key into a valid index between 0 and 999 (inclusive).

---

Data Structure per Bucket:

Each bucket is a linked list:

ListNode: (key, val, next)

We use a dummy head node for each list with:

key = -1, val = -1

This simplifies edge cases (e.g., deleting the first real node).

---

Core Operations:

put(key, value)

• Traverse the bucket's list.
• If key exists → update the value.
• If not → insert a new node at the end.

get(key)

• Traverse the bucket's list.
• Return the value if key found.
• Else, return -1.

remove(key)

• Traverse the list.
• If key matches → unlink the node from the list.

---

📊 Complexity Analysis

Let:

• n = total number of stored elements.
• k = number of buckets (1000 here).
• l = average number of elements per bucket = n / k.

• Worst-case time occurs when all keys hash to the same bucket (degenerating to a linked list).
• Average-case time is fast if the hash function distributes keys uniformly.

---

✅ Full Java Code

class ListNode {
    int key, val;
    ListNode next;
    public ListNode(int key, int val, ListNode next){
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

class MyHashMap {
    static final int size = 1000;          // Number of buckets
    private ListNode[] map;

    public MyHashMap() {
        map = new ListNode[size];
        // Initialize each bucket with a dummy head
        for (int i = 0; i < size; i++) {
            map[i] = new ListNode(-1, -1, null);
        }
    }

    public void put(int key, int value) {
        int hashed = hash(key);
        ListNode cur = map[hashed];

        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next.val = value;  // Key found, update value
                return;
            }
            cur = cur.next;
        }

        cur.next = new ListNode(key, value, null); // Key not found, insert new
    }

    public int get(int key) {
        int hashed = hash(key);
        ListNode cur = map[hashed].next;

        while (cur != null) {
            if (cur.key == key) return cur.val;
            cur = cur.next;
        }

        return -1;  // Not found
    }

    public void remove(int key) {
        int hashed = hash(key);
        ListNode cur = map[hashed];

        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next = cur.next.next;  // Skip the node to remove
                return;
            }
            cur = cur.next;
        }
    }

    private int hash(int key) {
        return key % size;
    }
}

---

🔄 Example Usage

MyHashMap map = new MyHashMap();

map.put(1, 100);
map.put(2, 200);
System.out.println(map.get(1));  // Output: 100
System.out.println(map.get(3));  // Output: -1

map.put(2, 300);
System.out.println(map.get(2));  // Output: 300

map.remove(2);
System.out.println(map.get(2));  // Output: -1

---

🧠 Key Takeaways

• This approach uses separate chaining with dummy heads for simplicity.
• It is a solid baseline implementation that mimics how hash tables work.
• In practice, Java's HashMap also resizes dynamically and treeifies buckets to improve performance.