HashMap Implementation from Scratch in DSA Python - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: You are building a simple phone book application. You want to store names and their phone numbers so you can quickly find a number by a name.To do this efficiently, you will create your own HashMap from scratch, which stores key-value pairs and allows fast lookup.

🎯 Goal: Build a basic HashMap class with methods to add key-value pairs and retrieve values by key.This will help you understand how hash maps work internally.

📋 What You'll Learn

Create a list of fixed size to store data

Create a hash function to convert keys to list indices

Implement a method to add key-value pairs

Implement a method to get values by key

Handle collisions by storing multiple items in the same bucket

💡 Why This Matters

🌍 Real World

HashMaps are used in many applications like phone books, caching, and databases to quickly find data by keys.

💼 Career

Understanding how hash maps work helps in software development roles that require efficient data storage and retrieval.

1

Create the storage list

Create a class called HashMap with an __init__ method that creates a list called buckets with 5 empty lists inside it.

DSA Python

class HashMap:
    def __init__(self):
        # Your code here

Hint

Use a list comprehension to create 5 empty lists inside self.buckets.

2

Add a hash function

Inside the HashMap class, add a method called _hash that takes self and key as parameters and returns the remainder of sum(ord(c) for c in key) divided by 5.

DSA Python

class HashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    # Add the _hash method below
    # Your code here

Hint

Use ord() to get ASCII values of characters and sum them.

3

Add key-value pairs

Add a method called put to the HashMap class that takes self, key, and value. Use _hash(key) to find the bucket index. If the key exists in that bucket, update its value. Otherwise, append the (key, value) tuple to the bucket.

DSA Python

class HashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    def _hash(self, key):
        return sum(ord(c) for c in key) % 5

    # Add the put method below
    # Your code here

Hint

Loop through the bucket to check if the key exists. If yes, update it. If no, add a new tuple.

4

Retrieve values by key

Add a method called get to the HashMap class that takes self and key. Use _hash(key) to find the bucket index. Search the bucket for the key and return its value if found. If not found, return None. Then, create a HashMap object, add these pairs: 'Alice': '123', 'Bob': '456', 'Charlie': '789', and print the result of get('Bob').

DSA Python

class HashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    def _hash(self, key):
        return sum(ord(c) for c in key) % 5

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    # Add the get method below
    # Your code here

# Create a HashMap object called phone_book
# Add the pairs 'Alice': '123', 'Bob': '456', 'Charlie': '789'
# Print the result of phone_book.get('Bob')
# Your code here

Hint

Loop through the bucket to find the key and return its value. Return None if not found.

Then create the phone_book object, add the pairs, and print phone_book.get('Bob').