Design HashMap -- Python Implementation

 

To design a hashmap, we need

1) hashing function -- will use hash() method 

2) an array for the hash table

3) Linkedlist for hash collision

class Node:

    def __init__(self, key, val, nxt=None):
        self.key = key
        self.val = val
        self.nxt = nxt


class LinkedList:

    def __init__(self):
        self.head = Node(0, 0)

    def append(self, key, val) -> None:
        prv, cur = self.head, self.head.nxt
        while cur is not None:
            if cur.key == key:
                cur.val = val
                return
            prv = cur
            cur = cur.nxt
        prv.nxt = Node(key, val)

    def find(self, key):
        cur = self.head.nxt
        while cur is not None:
            if cur.key == key:
                return cur.val
            cur = cur.nxt
        return False

    def remove(self, key) -> bool:
        prv, cur = self.head, self.head.nxt
        while cur is not None:
            if cur.key == key:
                prv.nxt = cur.nxt
                return True
            prv = cur
            cur = cur.nxt
        return False


class MyHashMap:

    def __init__(self):
        self.capacity = int(1e4)
        self.data = [LinkedList()] * self.capacity

    def put(self, key: int, value: int) -> None:
        # hash_value = hash(key) % self.size
        hash_value = hash(key) & (self.capacity - 1)
        self.data[hash_value].append(key, value)

    def get(self, key: int) -> int:
        hash_value = hash(key) & (self.capacity - 1)
        ret = self.data[hash_value].find(key)
        return ret if ret is not False else -1

    def remove(self, key: int) -> None:
        hash_value = hash(key) & (self.capacity - 1)
        self.data[hash_value].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)

*** hash_value can be calculated in either

hash_value = hash(key) % self.capacity

hash_value = hash(key) & (self.capacity - 1)

we use the latter one as it is computationally cheaper.

 

One huge limitation of the above is the usage of memory; capacity begins with 10**4. This is very inefficient if a hashmap contains a small number of elements -- we can improve the code to manage its size dynamically.

class Node:

    def __init__(self, key, val, nxt=None):
        self.key = key
        self.val = val
        self.nxt = nxt


class LinkedList:

    def __init__(self):
        self.head = Node(0, 0)

    def append(self, key, val) -> bool:
        prv, cur = self.head, self.head.nxt
        while cur is not None:
            if cur.key == key:
                cur.val = val
                return False
            prv = cur
            cur = cur.nxt
        prv.nxt = Node(key, val)
        return True

    def find(self, key):
        cur = self.head.nxt
        while cur is not None:
            if cur.key == key:
                return cur.val
            cur = cur.nxt
        return False

    def remove(self, key) -> bool:
        prv, cur = self.head, self.head.nxt
        while cur is not None:
            if cur.key == key:
                prv.nxt = cur.nxt
                return True
            prv = cur
            cur = cur.nxt
        return False

    def __iter__(self):
        cur = self.head.nxt
        while cur is not None:
            yield cur.key, cur.val
            cur = cur.nxt


class MyHashMap:

    def __init__(self):
        self.capacity = 4096
        self.cnt = 0
        self.data = [LinkedList()] * self.capacity

    def put(self, key: int, value: int) -> None:
        # hash_value = hash(key) % self.capacity
        hash_value = hash(key) & (self.capacity - 1)
        if self.data[hash_value].append(key, value) is True:
            self.cnt += 1
        if self.cnt == self.capacity:
            self.resize()

    def get(self, key: int) -> int:
        hash_value = hash(key) & (self.capacity - 1)
        ret = self.data[hash_value].find(key)
        return ret if ret is not False else -1

    def remove(self, key: int) -> None:
        hash_value = hash(key) & (self.capacity - 1)
        if self.data[hash_value].remove(key) is True:
            self.cnt -= 1

    def resize(self):
        self.capacity *= 2
        new_data = [LinkedList()] * self.capacity
        for ll in self.data:
            for k, v in ll:
                hash_value = hash(k) & (self.capacity - 1)
                new_data[hash_value].append(k, v)
        self.data = new_data


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

 

You can test the code here:

https://leetcode.com/problems/design-hashmap/description/?envType=daily-question&envId=2023-10-04 

LeetCode - The World's Leading Online Programming Learning Platform