LeetCode 706 - Design HashMap

LeetCode Problem 706

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Linked List, Design, Hash Function

Solution

Problem Understanding

The problem requires us to implement a HashMap from scratch without using any built-in hash table libraries. In other words, we need to create a data structure that can store key-value pairs, allow efficient insertion, retrieval, and deletion of values based on their keys. The input operations consist of put, get, and remove, and we must support up to 10,000 operations with keys and values in the range [0, 10^6].

The expected output for get is the value associated with a key, or -1 if the key does not exist. The put operation either inserts a new (key, value) pair or updates the value if the key already exists. The remove operation deletes the key and its value if it exists.

Key constraints and insights include that keys are non-negative integers and can go up to one million, meaning a naive array of size 10^6+1 would work but may be space-inefficient. Additionally, the number of operations (up to 10^4) allows solutions that are close to constant-time per operation. Edge cases to consider include inserting the same key multiple times, removing a non-existent key, or retrieving a key that has never been added.

Approaches

The brute-force approach is to use a simple list of tuples or an array of key-value pairs. Each operation (put, get, remove) would require scanning through the list to find the key, making each operation O(n) in the worst case. This is correct because it explicitly searches and updates the list for every operation, but it is inefficient for large numbers of operations.

The optimal approach is to implement a hash table using an array of buckets combined with separate chaining using linked lists. We use a hash function to map each key to a specific bucket index, and collisions are handled by maintaining a linked list in each bucket. This approach allows put, get, and remove operations to run in average-case O(1) time, assuming the hash function distributes keys evenly.

Algorithm Walkthrough

1. Initialize the hash map with a fixed number of buckets, each bucket being an empty linked list. The number of buckets is typically chosen as a prime number to reduce collisions.
2. Implement a hash function that maps a key to a bucket index using modulo arithmetic: bucket_index = key % number_of_buckets.
3. For put(key, value), calculate the bucket index. If the key exists in the bucket, update its value. If the key does not exist, append a new node with (key, value) to the linked list.
4. For get(key), calculate the bucket index and traverse the linked list in that bucket to find the node with the given key. Return its value if found, otherwise return -1.
5. For remove(key), calculate the bucket index and traverse the linked list to locate the node with the key. If found, remove the node from the linked list.

Why it works: The hash function ensures that keys are distributed across buckets, reducing the average number of elements per bucket. Linked lists in each bucket handle collisions, ensuring all keys can be stored and retrieved correctly.

Python Solution

class ListNode:
    def __init__(self, key: int, value: int, next=None):
        self.key = key
        self.value = value
        self.next = next

class MyHashMap:

    def __init__(self):
        self.size = 1009  # prime number of buckets
        self.buckets = [None] * self.size

    def _hash(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        if not self.buckets[index]:
            self.buckets[index] = ListNode(key, value)
            return
        current = self.buckets[index]
        while True:
            if current.key == key:
                current.value = value
                return
            if not current.next:
                break
            current = current.next
        current.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = self._hash(key)
        current = self.buckets[index]
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return -1

    def remove(self, key: int) -> None:
        index = self._hash(key)
        current = self.buckets[index]
        prev = None
        while current:
            if current.key == key:
                if prev:
                    prev.next = current.next
                else:
                    self.buckets[index] = current.next
                return
            prev, current = current, current.next

In this implementation, we first define a ListNode class to represent each key-value pair in the linked list. The MyHashMap class initializes an array of buckets. Each method uses the hash function to locate the correct bucket, then iterates through the linked list in that bucket to perform updates, retrievals, or deletions.

Go Solution

type ListNode struct {
    key, value int
    next       *ListNode
}

type MyHashMap struct {
    size    int
    buckets []*ListNode
}

func Constructor() MyHashMap {
    size := 1009
    buckets := make([]*ListNode, size)
    return MyHashMap{size: size, buckets: buckets}
}

func (this *MyHashMap) hash(key int) int {
    return key % this.size
}

func (this *MyHashMap) Put(key int, value int) {
    index := this.hash(key)
    if this.buckets[index] == nil {
        this.buckets[index] = &ListNode{key: key, value: value}
        return
    }
    current := this.buckets[index]
    for {
        if current.key == key {
            current.value = value
            return
        }
        if current.next == nil {
            break
        }
        current = current.next
    }
    current.next = &ListNode{key: key, value: value}
}

func (this *MyHashMap) Get(key int) int {
    index := this.hash(key)
    current := this.buckets[index]
    for current != nil {
        if current.key == key {
            return current.value
        }
        current = current.next
    }
    return -1
}

func (this *MyHashMap) Remove(key int) {
    index := this.hash(key)
    current := this.buckets[index]
    var prev *ListNode
    for current != nil {
        if current.key == key {
            if prev != nil {
                prev.next = current.next
            } else {
                this.buckets[index] = current.next
            }
            return
        }
        prev = current
        current = current.next
    }
}

In Go, we use pointers for the linked list nodes. The Put, Get, and Remove methods mirror the Python logic, with explicit handling of nil pointers for empty buckets or the head node.

Worked Examples

Example from the problem:

Complexity Analysis

The time complexity is dominated by the average number of elements per bucket. Choosing a prime number of buckets helps distribute keys evenly. Space complexity is linear in the number of keys stored.

Test Cases

# provided example
obj = MyHashMap()
obj.put(1, 1)
obj.put(2, 2)
assert obj.get(1) == 1  # key exists
assert obj.get(3) == -1 # key does not exist
obj.put(2, 1)
assert obj.get(2) == 1  # updated value
obj.remove(2)
assert obj.get(2) == -1 # removed key

# boundary tests
obj.put(0, 123)
assert obj.get(0) == 123
obj.put(10**6, 456)
assert obj.get(10**6) == 456
obj.remove(0)
assert obj.get(0) == -1

# stress test
for i in