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"))
Output:
Red Blue Green Yellow Purple