13.4 Design HashMap

13.4.1 Problem Metadata

13.4.2 Description

Implement a hash map supporting put(key, value), get(key), and remove(key) using separate chaining.

13.4.3 Examples

MyHashMap map = new MyHashMap();
map.put(1, 1);
map.put(2, 2);
map.get(1); // 1
map.get(3); // -1
map.put(2, 1); // update
map.get(2); // 1
map.remove(2);
map.get(2); // -1

13.4.4 Constraints

  • 0 <= key, value <= 10^6
  • At most 10^4 operations

13.4.5 Solution - Linked List Buckets

13.4.5.1 Walkthrough

Reuse the separate chaining idea but store key/value pairs in nodes. When inserting, update if the key already exists; otherwise add a new node at the bucket head. remove rewires the linked lc-list as needed.

13.4.5.2 Analysis

  • Time Complexity: Average O(1), worst-case O(n)
  • Space Complexity: O(n)

13.4.5.3 Implementation Steps

  1. Buckets array sized at 10,000 to balance collc-lisions.
  2. Hash function key % size.
  3. put: search for key; if found update value; else add new node.
  4. get: search bucket; return value or -1.
  5. remove: delete node from bucket lc-list.

13.4.5.4 Code - Java

class MyHashMap {
    private static class Node {
        int key, value;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final Node[] buckets;
    private final int size = 10000;

    public MyHashMap() {
        buckets = new Node[size];
    }

    public void put(int key, int value) {
        int idx = key % size;
        Node head = buckets[idx];
        Node curr = head;
        while (curr != null) {
            if (curr.key == key) {
                curr.value = value;
                return;
            }
            curr = curr.next;
        }
        Node node = new Node(key, value);
        node.next = head;
        buckets[idx] = node;
    }

    public int get(int key) {
        Node node = findNode(key);
        return node == null ? -1 : node.value;
    }

    public void remove(int key) {
        int idx = key % size;
        Node dummy = new Node(-1, -1);
        dummy.next = buckets[idx];
        Node prev = dummy;
        Node curr = dummy.next;
        while (curr != null) {
            if (curr.key == key) {
                prev.next = curr.next;
                break;
            }
            prev = curr;
            curr = curr.next;
        }
        buckets[idx] = dummy.next;
    }

    private Node findNode(int key) {
        int idx = key % size;
        Node curr = buckets[idx];
        while (curr != null) {
            if (curr.key == key) {
                return curr;
            }
            curr = curr.next;
        }
        return null;
    }
}