Hash Map In Python

July 7, 2021

Hash maps are indexed data structures. A hash map uses a hash function to compute an index with a key/value into an array of buckets. Its value is mapped to the bucket with the corresponding index. The key is unique just like a currency note and these keys are immutable.

Think of a cabinet having drawers with labels for the items stored in them. Here,

The cabinet is the hash map.
The drawers with labels are the buckets.
The user’s email or User ID is the key.
The user’s details such as name, bank number, contact number are the values.
These values get mapped to the buckets.

The fundamental implementation of a hash map is done using a Hash function. It accepts a key and translates it to the index of a bucket in the bucket list. Each and every key must have a different index in Ideal Hashing. However, the collisions (When hashing gives an existing index) still may occur. We can use rehashing techniques or maybe a bucket to store multiple values by appending a list.

In Python, dictionaries are examples of hash maps.

The hash map design will include the functions that follow:

set_val(key, value): Enters a key-value pair into the hash map. If the value already exists in the hash map, it updates the value.

get_val(key): Returns the value to which the specified key is mapped, or returns “No record found” if it finds no mapping for the key.

delete_val(key): Removes the mapping for the specific key, if the key is found mapped.

What makes a Hash Table different from a Hashmap?

Hash Table:

They are synchronized and fast.
Allow more than one null value
They allow only one null key.

Hash Map:

They are unsynchronized and slow.
Null values or null keys are not allowed.

The search complexity of a hash map is O(1).

#Code for hash map implementation

>>class Node:
def __init__(self, key, value):
     self.key = key
     self.value = value
     self.next = None
 
>>class hashmap:
def __init__(self):
     self.store = [None for _ in range(n)]
def get(self, key):
     index = hash(key) & n-1                   
     if self.store[index] is None:
         return None
     p = self.store[index]
     while True:
         if p.key == key:
             return p.value
         else:
             if n.next:
                 p = p.next
             else:
                    return None
def put(self, key, value):
     nd = Node(key, value)
     index = hash(key) & n-1
     p = self.store[index]
     if p is None:
            self.store[index] = nd
     else:
         if p.key == key:
             p.value = value
         else:
             while p.next:
                 if p.key == key:
                        p.value = value
                        return
                    else:
                        p = p.next
             p.next = nd
>>hm = hashmap()
>>hm.set("1", "red")
>>hm.set("2", "blue")
>>hm.set("3", "green")
>>hm.set("4", "yellow")
>>hm.set("5", "purple")
>>print(hm.get("1"))
>>print(hm.get("2"))
>>print(hm.get("3"))
>>print(hm.get("4"))
>>print(hm.get("5"))