HashMap Implementation from Scratch in DSA Python - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Start

↓

Compute hash(key)

↓

Find bucket index = hash % capacity

↓

Check bucket for key

↓

Key found?

↓

Update value

↓

Done

↓

Add new key-value pair

↓

Done

The flow shows how a key is hashed to find a bucket, then the bucket is checked for the key. If found, update value; if not, add new pair.

Execution Sample

DSA Python

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

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

This code initializes a hashmap with 4 buckets and starts the put operation by computing the bucket index.

Execution Table

Step	Operation	Key	Value	Bucket Index	Bucket Before	Bucket After	Visual State
1	Initialize HashMap	-	-	-	[]	[]	[[], [], [], []]
2	put('apple', 10)	apple	10	3	[]	[('apple', 10)]	[[], [], [], [('apple', 10)]]
3	put('banana', 20)	banana	20	0	[]	[('banana', 20)]	[[('banana', 20)], [], [], [('apple', 10)]]
4	put('apple', 15) update	apple	15	3	[('apple', 10)]	[('apple', 15)]	[[('banana', 20)], [], [], [('apple', 15)]]
5	put('grape', 30)	grape	30	2	[]	[('grape', 30)]	[[('banana', 20)], [], [('grape', 30)], [('apple', 15)]]
6	put('melon', 40)	melon	40	1	[]	[('melon', 40)]	[[('banana', 20)], [('melon', 40)], [('grape', 30)], [('apple', 15)]]
7	put('banana', 25) update	banana	25	0	[('banana', 20)]	[('banana', 25)]	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15)]]
8	put('kiwi', 50)	kiwi	50	3	[('apple', 15)]	[('apple', 15), ('kiwi', 50)]	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15), ('kiwi', 50)]]
9	End of operations	-	-	-	-	-	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15), ('kiwi', 50)]]

💡 All put operations completed, hashmap buckets updated accordingly.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
buckets	[[], [], [], []]	[[], [], [], [('apple', 10)]]	[[('banana', 20)], [], [], [('apple', 10)]]	[[('banana', 20)], [], [], [('apple', 15)]]	[[('banana', 20)], [], [('grape', 30)], [('apple', 15)]]	[[('banana', 20)], [('melon', 40)], [('grape', 30)], [('apple', 15)]]	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15)]]	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15), ('kiwi', 50)]]	[[('banana', 25)], [('melon', 40)], [('grape', 30)], [('apple', 15), ('kiwi', 50)]]

Key Moments - 3 Insights

Why do we use hash(key) % capacity to find the bucket index?

Because hash(key) can be a very large number, using modulo with capacity ensures the index fits within the fixed number of buckets, as shown in steps 2-8 in the execution_table.

What happens if the key already exists in the bucket?

We find the key in the bucket and update its value instead of adding a new pair, as seen in steps 4 and 7 where 'apple' and 'banana' values are updated.

Why do buckets hold lists of key-value pairs?

Because multiple keys can hash to the same bucket index (collision), so we store pairs in a list to handle collisions, demonstrated by step 8 where 'apple' and 'kiwi' share bucket 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the bucket index for key 'apple'?

A 1

B 3

C 0

D 2

💡 Hint

Check the 'Bucket Index' column at step 4 in the execution_table.

At which step does the bucket for index 0 get updated with a new value for 'banana'?

A Step 2

B Step 3

C Step 7

D Step 8

💡 Hint

Look for 'banana' updates in the 'Operation' column and bucket changes at index 0.

If we add a new key 'pear' that hashes to bucket 2, what will happen to the bucket at index 2?

A It will add ('pear', value) to the list

B It will replace existing pairs

C It will clear the bucket

D It will cause an error

💡 Hint

Buckets hold lists of pairs to handle collisions, as shown in step 8 where multiple pairs exist in one bucket.

Concept Snapshot

HashMap stores key-value pairs in buckets.
Hash function maps key to bucket index using modulo.
Each bucket holds a list to handle collisions.
put(key, value) adds or updates pairs in the bucket.
Lookup uses same hash and bucket to find value.
Simple, fast average access by key.

Full Transcript

This visual execution traces a simple HashMap implementation from scratch. The HashMap has a fixed capacity of 4 buckets, each a list to hold key-value pairs. When putting a key-value pair, the key is hashed and modulo applied to find the bucket index. The bucket is checked for the key; if found, the value is updated, else the pair is added. The execution table shows step-by-step how keys like 'apple', 'banana', 'grape', 'melon', and 'kiwi' are added or updated in their respective buckets. The variable tracker shows the bucket states after each operation. Key moments clarify why modulo is used, how updates happen, and why buckets hold lists. The visual quiz tests understanding of bucket indexing, updates, and collision handling. The concept snapshot summarizes the core ideas of HashMap storage and operations.

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