HashMap Implementation from Scratch in DSA Python

Mental Model

A HashMap stores key-value pairs by turning keys into indexes to quickly find values.

Analogy: Imagine a library where each book has a unique code. Instead of searching all shelves, you use the code to go directly to the right shelf and find the book fast.

Buckets array: [null, null, null, null, null]
Each bucket can hold a linked list of entries:
Bucket 0 -> null
Bucket 1 -> null
Bucket 2 -> null
Bucket 3 -> null
Bucket 4 -> null

Dry Run Walkthrough

Input: Insert key-value pairs: (1, 'apple'), (6, 'banana'), (11, 'cherry') into a HashMap with 5 buckets

Goal: Store all pairs so that keys with same bucket index are chained, and values can be retrieved quickly

Step 1: Insert (1, 'apple'): compute bucket index 1 % 5 = 1, bucket 1 is empty, add node

Buckets:
[null, (1:'apple') -> null, null, null, null]

Why: We place the first key-value pair in its bucket directly

Step 2: Insert (6, 'banana'): compute bucket index 6 % 5 = 1, bucket 1 has (1:'apple'), add new node at head

Buckets:
[null, (6:'banana') -> (1:'apple') -> null, null, null, null]

Why: Collision occurs, so we chain new node at bucket 1's linked list head

Step 3: Insert (11, 'cherry'): compute bucket index 11 % 5 = 1, bucket 1 has two nodes, add new node at head

Buckets:
[null, (11:'cherry') -> (6:'banana') -> (1:'apple') -> null, null, null, null]

Why: Another collision, so we add new node at head of bucket 1's chain

Step 4: Retrieve value for key 6: compute bucket 1, traverse nodes (11:'cherry'), (6:'banana') found key 6

Buckets unchanged:
[null, (11:'cherry') -> (6:'banana') -> (1:'apple') -> null, null, null, null]

Why: We find the value by checking nodes in the bucket's chain

Result:

Buckets:
[null, (11:'cherry') -> (6:'banana') -> (1:'apple') -> null, null, null, null]
Value for key 6: 'banana'

Annotated Code

DSA Python

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashMap:
    def __init__(self, size=5):
        self.size = size
        self.buckets = [None] * size

    def _hash(self, key):
        return key % self.size

    def put(self, key, value):
        index = self._hash(key)  # find bucket index
        head = self.buckets[index]

        # Check if key exists, update value
        curr = head
        while curr:
            if curr.key == key:
                curr.value = value  # update existing key
                return
            curr = curr.next

        # Insert new node at head
        new_node = Node(key, value)
        new_node.next = head
        self.buckets[index] = new_node

    def get(self, key):
        index = self._hash(key)  # find bucket index
        curr = self.buckets[index]
        while curr:
            if curr.key == key:
                return curr.value  # found value
            curr = curr.next
        return None  # key not found

    def __str__(self):
        result = []
        for i, node in enumerate(self.buckets):
            chain = []
            curr = node
            while curr:
                chain.append(f"({curr.key}: '{curr.value}')")
                curr = curr.next
            chain_str = " -> ".join(chain) + " -> null" if chain else "null"
            result.append(f"Bucket {i}: {chain_str}")
        return "\n".join(result)

# Driver code
hash_map = HashMap()
hash_map.put(1, 'apple')
hash_map.put(6, 'banana')
hash_map.put(11, 'cherry')
print(hash_map)
print("Value for key 6:", hash_map.get(6))

index = self._hash(key) # find bucket index

compute bucket index from key

while curr: if curr.key == key: curr.value = value return

search bucket chain to update existing key's value

new_node.next = head self.buckets[index] = new_node

insert new node at head of bucket chain

while curr: if curr.key == key: return curr.value

search bucket chain to find value for key

Output

Bucket 0: null

Bucket 1: (11: 'cherry') -> (6: 'banana') -> (1: 'apple') -> null

Bucket 2: null

Bucket 3: null

Bucket 4: null

Value for key 6: banana

Complexity Analysis

Time: O(n/k) average, where n is number of keys and k is bucket count, because each bucket chain is short on average

Space: O(n) because we store all key-value pairs in nodes

vs Alternative: Compared to a simple list which is O(n) for search, this reduces average search to O(1) by using hashing and chaining

Edge Cases

Insert duplicate key with new value

Value is updated in existing node instead of adding new node

DSA Python

if curr.key == key:
    curr.value = value  # update existing key
    return

Get value for key not present

Returns None indicating key not found

DSA Python

return None  # key not found

Empty HashMap get operation

Returns None since no keys exist

DSA Python

return None  # key not found

When to Use This Pattern

When you need fast key-value storage with quick insert and lookup, and keys can collide, use a HashMap with chaining to handle collisions efficiently.

Common Mistakes

Mistake: Not handling collisions, overwriting existing nodes in bucket
Fix: Use linked list chaining to store multiple nodes in the same bucket

Mistake: Not updating value when inserting duplicate key
Fix: Check for existing key in bucket chain and update its value instead of adding new node

Summary

Stores key-value pairs using hashing and linked list chaining to handle collisions.

Use when you want fast average-time insert and lookup by key.

The key insight is to convert keys to bucket indexes and chain collided entries in linked lists.

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