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').

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store key-value pairs for fast data retrieval

B. To store data in a sorted order

C. To perform mathematical calculations

D. To store data in a sequential list

Solution

1. Step 1: Understand what a HashMap stores

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Identify the main purpose

   The main purpose is to retrieve data quickly by keys, not to sort or calculate.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option A

4. Quick Check:

   HashMap = fast key-value access [OK]

Hint: Remember: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Confusing HashMap with sorted data structures
• Thinking HashMap stores data sequentially
• Assuming HashMap is for calculations

2. Which of the following is the correct way to define a simple HashMap class constructor in Python?

easy

A. def __init__(self): self.map = set()

B. def __init__(self): self.map = []

C. def __init__(self): self.map = {}

D. def __init__(self): self.map = ()

Solution

1. Step 1: Identify the data structure for storing key-value pairs

   A HashMap stores key-value pairs, so a dictionary {} is appropriate.

2. Step 2: Check each option's data type

   def __init__(self): self.map = {} uses {} which is a dictionary. Others use list, set, or tuple which are not suitable for key-value mapping.

3. Final Answer:

   def __init__(self): self.map = {} -> Option C

4. Quick Check:

   HashMap uses dictionary = {} [OK]

Hint: Use {} to store key-value pairs in Python [OK]

Common Mistakes:

• Using list or tuple instead of dictionary
• Confusing set with dictionary
• Not initializing the map attribute

3. What will be the output of the following code?

class HashMap:
    def __init__(self):
        self.map = {}
    def put(self, key, value):
        self.map[key] = value
    def get(self, key):
        return self.map.get(key, None)

h = HashMap()
h.put('a', 1)
h.put('b', 2)
print(h.get('a'))
print(h.get('c'))

medium

A. 1\nNone

B. 1\n0

C. None\nNone

D. Error

Solution

1. Step 1: Trace the put method calls

   Keys 'a' and 'b' are added with values 1 and 2 respectively.

2. Step 2: Trace the get method calls

   Getting 'a' returns 1. Getting 'c' returns None because 'c' is not in the map and default is None.

3. Final Answer:

   1\nNone -> Option A

4. Quick Check:

   Existing key returns value, missing key returns None [OK]

Hint: get() returns None if key not found by default [OK]

Common Mistakes:

• Expecting 0 instead of None for missing keys
• Confusing print output format
• Assuming error on missing key

4. Find the error in this HashMap implementation snippet:

class HashMap:
    def __init__(self):
        self.map = []
    def put(self, key, value):
        self.map[key] = value

medium

A. Missing return statement in put method

B. No error, code is correct

C. Incorrect method name put instead of add

D. Using list instead of dictionary for self.map

Solution

1. Step 1: Check the data structure used for self.map

   self.map is initialized as a list, but lists do not support key-based assignment.

2. Step 2: Understand why list causes error

   Using self.map[key] = value will cause TypeError because list indices must be integers, not keys.

3. Final Answer:

   Using list instead of dictionary for self.map -> Option D

4. Quick Check:

   List can't use keys as indices [OK]

Hint: Use dictionary {} for key-value storage, not list [] [OK]

Common Mistakes:

• Thinking put method needs return
• Confusing method names
• Ignoring data type of self.map

5. You want to implement a HashMap that handles collisions by chaining (using lists). Which of the following code snippets correctly initializes the internal storage for chaining?

hard

A. self.map = {}

B. self.map = [[] for _ in range(size)]

C. self.map = [None] * size

D. self.map = [0] * size

Solution

1. Step 1: Understand chaining collision handling

   Chaining uses a list of lists where each bucket holds a list of key-value pairs.

2. Step 2: Identify correct initialization

   self.map = [[] for _ in range(size)] creates a list of empty lists, one for each bucket, suitable for chaining.

3. Step 3: Why other options are incorrect

   self.map = [None] * size creates a list of None, which needs extra checks. self.map = {} is a dictionary, not a list of buckets. self.map = [0] * size creates a list of zeros, not suitable for chaining.

4. Final Answer:

   self.map = [[] for _ in range(size)] -> Option B

5. Quick Check:

   Chaining needs list of lists = [[] for _ in range(size)] [OK]

Hint: Use list comprehension to create buckets for chaining [OK]

Common Mistakes:

• Using None or 0 instead of empty lists for buckets
• Confusing dictionary with list of buckets
• Not initializing buckets properly for chaining