HashMap in Python

Board Infinity -

Introduction

Hash maps are the indexed Data Strutures. When creating an index with a key into an array of buckets or slots, a hash map uses a hash function. The bucket with the corresponding index is linked to its value. The key is distinct and unchangeable. Imagine a hash map as a cabinet with drawers that are labelled for the items inside of them. For instance, when storing user data, we can map values for the user, such as their first and last names, to a bucket by using their email address as the key.

Implementing a hash map relies primarily on hash functions. It accepts the key and converts it to the bucket index from the key. A different index should be generated by ideal hashing for each key. But collisions can happen. We can easily use a bucket for multiple values by appending a list or by rehashing when hashing yields an existing index.

Dictionaries are an illustration of hash maps in Python. To learn how to create and modify such data structures for search optimization, we'll see a hash map implemented from scratch.

Functions

The Hash Map we will be designing will have the Following functions:

  • set(key, value): This will Insert a key-value pair into the hash map. If the value already exists in the hash map, this will update the value.
  • get(key): This will returns the value to which the specified key is mapped, or “No record found” if this map contains no mapping for the key.
  • delete(key): This will remove the mapping for the specific key if the hash map contains the mapping for the key.

Code Implementation

Let's Implement hashmap using dictionary in python.

Example 1:

def set(key, value):
    if(key in hashmap):
        hashmap[key].append(value)
    else:
        hashmap[key] = [value]

def get(key):
    if(key in hashmap):
        return hashmap[key]
    else:
        return "Key not in hashmap"
       

def delete(key):
    if(key in hashmap):
        del hashmap[key]
    else:
        return "Key not in hashmap"
       
hashmap = {}

set("A", 1)
set("A", 2)
set("A", 3)
set("B", 1)
set("B", 2)

print(hashmap)

print(get("A"))
print(get("B"))
print(get("C"))

delete("A")

print(hashmap)

Output:

{'A': [1, 2, 3], 'B': [1, 2]}
[1, 2, 3]
[1, 2]
Key not in hashmap
{'B': [1, 2]}

write your code here: Coding Playground

Example 2:

def set(key, value):
    if(key in hashmap):
        hashmap[key].append(value)
    else:
        hashmap[key] = [value]

def get(key):
    if(key in hashmap):
        return hashmap[key]
    else:
        return "Key not in hashmap"
       

def delete(key):
    if(key in hashmap):
        del hashmap[key]
    else:
        return "Key not in hashmap"
       
hashmap = {}

set(1, "One")
set(1, "One")
set(2, "Two")
set(3, "Three")
set(4, "Four")

print("Hashmap:", hashmap)

print(get(1))
print(get(2))
print(get(3))

delete(3)
delete(3)

print("Hashmap:", hashmap)

Output:

Hashmap: {1: ['One', 'One'], 2: ['Two'], 3: ['Three'], 4: ['Four']}
['One', 'One']
['Two']
['Three']
Hashmap: {1: ['One', 'One'], 2: ['Two'], 4: ['Four']}

write your code here: Coding Playground

Time Complexity

Hashing and memory index access both take a fixed amount of time. As a result, a hash map's search complexity is also constant time, or O(1).