LeetCode 706: Design HashMap

Indexed sequence

Since $0 \le \texttt{key} \le 10^6$ , we can use a list of length $10^6+1$ to implement the API.

Total space is $\mathcal{O}(|\texttt{key-domain}|)$ .

class MyHashMap:

    def __init__(self):
        self.data = [-1] * 1_000_001

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key]

    def remove(self, key: int) -> None:
        self.data[key] = -1


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Linked list

We can use a doubly linked list where an item is $(\texttt{key}, \texttt{value})$ .

Total space is $\mathcal{O}(\texttt{key-count})$ .

class ListNode:
    def __init__(self, item=None):
        self.item = item
        self.prev, self.next = None, None

class LinkedList:
    def __init__(self):
        self.root = ListNode()

    def __get_node(self, key):
        t = self.root
        while t.next:
            t = t.next
            k, v = t.item
            if k == key:
                return True, t
        return False, t
    
    def put(self, key, value):
        item = (key, value)
        found, node = self.__get_node(key)
        if found:
            node.item = item
            return
        tail = ListNode(item)
        node.next = tail
        tail.prev = node

    def get(self, key):
        found, node = self.__get_node(key)
        if found:
            _, value = node.item
            return value
        return -1

    def remove(self, key):
        found, node = self.__get_node(key)
        if not found:
            return
        prev_node, next_node = node.prev, node.next
        prev_node.next = next_node
        if next_node:
            next_node.prev = prev_node
        node.next, node.prev = None, None

class MyHashMap:

    def __init__(self):
        self.data = LinkedList()

    def put(self, key: int, value: int) -> None:
        self.data.put(key, value)
        
    def get(self, key: int) -> int:
        return self.data.get(key)

    def remove(self, key: int) -> None:
        self.data.remove(key)

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Indexed sequence of linked lists

We can use a combination of indexed sequence and linked lists to strike a balance between time and space complexities.

Say there are $K$ keys and len(self.data) = $M$ . As long as __hash(key)is uniformly distributed among the indices $[0, M-1]$ , the amortized time complexity of each operation is proportional to $\texttt{load-factor} = \frac{K}{M}$ .

Total space is $\mathcal{O}(M + \texttt{key-count})$ .

class ListNode:
    def __init__(self, item=None):
        self.item = item
        self.prev, self.next = None, None

class LinkedList:
    def __init__(self):
        self.root = ListNode()

    def __get_node(self, key):
        t = self.root
        while t.next:
            t = t.next
            k, v = t.item
            if k == key:
                return True, t
        return False, t
    
    def put(self, key, value):
        item = (key, value)
        found, node = self.__get_node(key)
        if found:
            node.item = item
            return
        tail = ListNode(item)
        node.next = tail
        tail.prev = node

    def get(self, key):
        found, node = self.__get_node(key)
        if found:
            _, value = node.item
            return value
        return -1

    def remove(self, key):
        found, node = self.__get_node(key)
        if not found:
            return
        prev_node, next_node = node.prev, node.next
        prev_node.next = next_node
        if next_node:
            next_node.prev = prev_node
        node.next, node.prev = None, None

class MyHashMap:

    def __init__(self):
        self.data = [None] * 997

    def __hash(self, key):
        return key % len(self.data)

    def put(self, key: int, value: int) -> None:
        h = self.__hash(key)
        if not self.data[h]:
            self.data[h] = LinkedList()
        self.data[h].put(key, value)
        
    def get(self, key: int) -> int:
        h = self.__hash(key)
        return self.data[h].get(key) if self.data[h] else -1

    def remove(self, key: int) -> None:
        h = self.__hash(key)
        if not self.data[h]:
            return
        self.data[h].remove(key)

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

If $K$ grows, with a fixed $M$ , the $\texttt{load-factor}$ grows — making the operations slower. We can adapt $M$ so that $\texttt{load-factor}$ remains below $0.5$ .

class ListNode:
    def __init__(self, item=None):
        self.item = item
        self.prev, self.next = None, None

class LinkedList:
    def __init__(self):
        self.root = ListNode()

    def __get_node(self, key):
        t = self.root
        while t.next:
            t = t.next
            k, v = t.item
            if k == key:
                return True, t
        return False, t
    
    def put(self, key, value):
        item = (key, value)
        found, node = self.__get_node(key)
        if found:
            node.item = item
            return True
        tail = ListNode(item)
        node.next = tail
        tail.prev = node
        return False

    def items(self):
        t = self.root
        while t.next:
            t = t.next
            yield t.item

    def get(self, key):
        found, node = self.__get_node(key)
        if found:
            _, value = node.item
            return value
        return -1

    def remove(self, key):
        found, node = self.__get_node(key)
        if not found:
            return False
        prev_node, next_node = node.prev, node.next
        prev_node.next = next_node
        if next_node:
            next_node.prev = prev_node
        node.next, node.prev = None, None
        return True

class MyHashMap:

    def __init__(self):
        self.key_count = 0
        self.data = [None] * 31

    def __hash(self, key):
        return key % len(self.data)

    def __resize(self, capacity):
        buckets = [None] * capacity
        for ll in self.data:
            if not ll:
                continue
            for item in ll.items():
                k, v = item
                h = k % len(buckets)
                if not buckets[h]:
                    buckets[h] = LinkedList()
                buckets[h].put(k, v)
        self.data = buckets

    def put(self, key: int, value: int) -> None:
        if self.key_count >= len(self.data) // 2:
            self.__resize(2 * len(self.data))

        h = self.__hash(key)
        if not self.data[h]:
            self.data[h] = LinkedList()
        added = self.data[h].put(key, value)
        if added:
            self.key_count += 1
        
    def get(self, key: int) -> int:
        h = self.__hash(key)
        return self.data[h].get(key) if self.data[h] else -1

    def remove(self, key: int) -> None:
        h = self.__hash(key)
        if not self.data[h]:
            return
        deleted = self.data[h].remove(key)
        if deleted:
            self.key_count -= 1
        
        # Say len(data) = 4 and key_count reaches 2.
        # We now double, so that len(data) = 8 and key_count = 2.
        # If we shrunk on key_count <= len(self.data) // 4, we would have 
        # immediately issued a resize (to shrink). Thus perennial resize's commence.
        # To avoid that, before we trigger shrink, we wait until key_count <= len(self.data) // 8.
        if 0 < self.key_count <= len(self.data) // 8:
            self.__resize(len(self.data) // 2)

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Operation	Time	Space
`put`	$\mathcal{O}(1)$	$\mathcal{O}(1)$
`get`	$\mathcal{O}(1)$	$\mathcal{O}(1)$
`remove`	$\mathcal{O}(1)$	$\mathcal{O}(1)$

Operation	Time	Space
`put`	$\mathcal{O}(n)$	$\mathcal{O}(1)$
`get`	$\mathcal{O}(n)$	$\mathcal{O}(1)$
`remove`	$\mathcal{O}(n)$	$\mathcal{O}(1)$

Operation	Time	Space
`put`	$\mathcal{O}(\texttt{load-factor})$	$\mathcal{O}(1)$
`get`	$\mathcal{O}(\texttt{load-factor})$	$\mathcal{O}(1)$
`remove`	$\mathcal{O}(\texttt{load-factor})$	$\mathcal{O}(1)$

unreasonably effective