Design HashMap in Python

Suppose we want to design a HashMap without using any built-in hash table libraries. There will be different functions as follows −

• put(key, value) − This will insert a value associated with key into the HashMap. If the value already exists in the HashMap, update the value.
• get(key) − This will return the value to which the specified key is mapped, otherwise -1 when this map contains no mapping for the key.
• remove(key) − This will Remove the mapping for the value key if this map contains the mapping for the key.

So, if the input is like After initialization, call the put and get methods as follows −

• put(1, 1);
• put(2, 2);
• get(1);
• get(3);
• put(2, 1);
• get(2);
• remove(2);
• get(2);

then the output will be 1, -1(not present), 1, -1(not present) respectively.

To solve this, we will follow these steps −

• Create a new data structure called node, and to initialize it, there will be some fields like(key, val, next) , next is initially null
• Define one Linked list, there are few methods as follows −
• Define one initializer, this will work as follows −
  • prehead := a new node Node with key = null and val = null
• Define a function search(). This will take key
• p := prehead.next
• while p is not null, do
  • if p.key is same as key, then
    • return p
  • p := p.next
• return None
• Define a function add(). This will take key, val
• p := search(key)
• if p is not null, then
  • p.val := val
• otherwise,
  • node := new Node with (key, val)
  • prehead.next := node, node.next := prehead.next
• Define a function get(). This will take key
• p := search(key)
• if p is not null, then
  • return p.val
• otherwise,
  • return null
• Define a function remove. This will take key
• prev := prehead
• cur := prev.next
• while cur is not null, do
  • if cur.key is same as key, then
    • come out from the loop
  • prev := curr, cur := cur.next
  • if cur is not null, then
    • prev.next := cur.next
• Define a function serialize().
• p := prehead.next
• ret := a new list
• while p is not null, do
  • insert [p.key, p.val] into ret at the end
  • p := p.next
• return ret
• From the custom hashmap, define methods as follows −
• Define a one initializer.
• size := 1033
• arr := an array of LinkedList() whose length is same as size
• Define a function _hash(). This will take key
• return key mod size
• Define a function put() . This will take key, value
• h := _hash(key)
• add(key, value) of arr[h]
• Define a function get(). This will take key
• h := _hash(key)
• ret := get(key) of arr[h]
• if ret is not null, then
  • return ret
• otherwise,
  • return -1
• Define a function remove(). This will take key
• h := _hash(key)
• delete key from arr[h]

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Node:    def __init__(self, key, val):       self.key = key       self.val = val       self.next = None class LinkedList:    def __init__(self):       self.prehead = Node(None, None)    def search(self, key):       p = self.prehead.next       while p:          if p.key == key:             return p          p = p.next       return None    def add(self, key, val):       p = self.search(key)       if p:          p.val = val       else:          node = Node(key, val)          self.prehead.next, node.next = node, self.prehead.next    def get(self, key):       p = self.search(key)       if p:          return p.val       else:          return None    def remove(self, key):       prev = self.prehead       cur = prev.next       while cur:          if cur.key == key:             break          prev, cur = cur, cur.next       if cur:          prev.next = cur.next    def serialize(self):       p = self.prehead.next       ret = []       while p:          ret.append([p.key, p.val])          p = p.next       return ret class MyHashMap:    def __init__(self):       self.size = 1033       self.arr = [LinkedList() for _ in range(self.size)]    def _hash(self, key):       return key % self.size    def put(self, key, value):       h = self._hash(key)       self.arr[h].add(key, value)    def get(self, key):       h = self._hash(key)       ret = self.arr[h].get(key)       if ret is not None:          return ret       else:          return -1    def remove(self, key):       h = self._hash(key)       self.arr[h].remove(key) ob = MyHashMap() ob.put(1, 1) ob.put(2, 2) print(ob.get(1)) print(ob.get(3)) ob.put(2, 1) print(ob.get(2)) ob.remove(2) print(ob.get(2))

Input

ob = MyHashMap() ob.put(1, 1) ob.put(2, 2) print(ob.get(1)) print(ob.get(3)) ob.put(2, 1) print(ob.get(2)) ob.remove(2) print(ob.get(2))

Output

1 -1 1 -1