Hash Map in Python
Here in this tutorial, we will learn about Hash Maps in Python.
A Hash map is a data structure where data is stored in key and value format where all the keys are unique and for a particular key, there will be a particular value.
In a hashmap, the main focus is on the key as through the key we will be able to access and insert data.
First of all, we need to be familiar with some terms:
- Bucket Array: An array/list used for storing and accessing elements.
- Hash function: To convert the key into an integer to know exactly where the key is to be inserted or through where the key is to be accessed.
The Hash function will be responsible for two things:
- Hash code: Provide an integer larger than the bucket size.
- Compression function: Compress the integer to fit within the bucket size limits through “% bucket size”.
But to prevent getting the same index for two different keys through the hash function that is to prevent collision we have two methods:
- Closed hashing/Separate chaining: Store multiple elements at one position in the form of a linked list.
- Open addressing: Store somewhere else if the index is already full.
Insertion in HashMap
class mapNode: def __init__(self, key, value): self.key = key self.value = value self.next = None class HashMap: def __init__(self): self.bucketsize = 10 self.bucket = [None for i in range(self.bucketsize)] self.count = 0 def mapSize(self): return self.count def compression(self, hashcode): return (abs(hashcode) % (self.bucketsize)) def insertion(self, key, value): hashcode = hash(key) index = self.compression(hashcode) head = self.bucket[index] while head != None: if head.key == key: head.value = value return head = head.next newnode = mapNode(key, value) newnode.next = head self.bucket[index] = newnode self.count += 1 map = HashMap() map.insertion('abc', 5) map.insertion('bca', 8) print(map.mapSize())
In the code written above, we have firstly declared a node class that will be responsible for creating a new node with key and value.
Then we made a hashmap with bucket size 10 for the instant with all elements to be None and a count of “0” as there are no elements.
Moving forward we have the
mapSize() method which will return the size of the map and the
compression() method which will take the hashcode and compress it to fit the bucket size.
Then we have an insertion() method which will take care of hashcode generation and assign value to a new head once created and increase the count accordingly.
In the end, we will insert elements and get the final number of elements printed.
Thus we have learned about Hashmap and how it works in Python.