HashMap Implementation from Scratch in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Basic HashMap Put and Get Operations

What is the output of the following code that uses a simple HashMap implementation to store and retrieve values?

DSA Python

class SimpleHashMap:
    def __init__(self):
        self.size = 5
        self.map = [[] for _ in range(self.size)]

    def _get_hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        key_hash = self._get_hash(key)
        key_exists = False
        bucket = self.map[key_hash]
        for i, kv in enumerate(bucket):
            k, v = kv
            if k == key:
                bucket[i] = (key, value)
                key_exists = True
                break
        if not key_exists:
            bucket.append((key, value))

    def get(self, key):
        key_hash = self._get_hash(key)
        bucket = self.map[key_hash]
        for k, v in bucket:
            if k == key:
                return v
        return None

hm = SimpleHashMap()
hm.put('apple', 10)
hm.put('banana', 20)
hm.put('apple', 30)
print(hm.get('apple'))
print(hm.get('banana'))
print(hm.get('cherry'))

A 30\n20\n0

B 30\n20\nNone

C 10\n20\nNone

D None\nNone\nNone

💡 Hint

Think about what happens when you put a value for an existing key.

The 'apple' key is first set to 10, then updated to 30. 'banana' is set to 20. 'cherry' is not in the map, so get returns None.

🧠 Conceptual

intermediate

Understanding HashMap Collision Handling

In a HashMap implemented with separate chaining (using lists for buckets), what happens when two different keys produce the same hash index?

A Both key-value pairs are stored in the same bucket list at that index.

B The second key-value pair overwrites the first one at that index.

C The HashMap throws an error due to collision.

D The HashMap automatically resizes to avoid collision.

💡 Hint

Think about how separate chaining works to handle collisions.

Separate chaining stores multiple key-value pairs in a list at the same index to handle collisions.

🔧 Debug

advanced

Identify the Bug in HashMap Remove Method

Consider this remove method in a HashMap implementation. What error will occur when trying to remove a key not present in the map?

DSA Python

def remove(self, key):
    key_hash = self._get_hash(key)
    bucket = self.map[key_hash]
    for i, kv in enumerate(bucket):
        k, v = kv
        if k == key:
            del bucket[i]
            return True
    return False

hm = SimpleHashMap()
hm.put('a', 1)
hm.remove('b')

A TypeError because bucket is None.

B IndexError because del bucket[i] tries to delete invalid index.

C No error; returns False because key not found.

D KeyError because key 'b' is not in the map.

💡 Hint

What does the method return if the key is not found?

The method returns False if the key is not found, so no error occurs.

❓ Predict Output

advanced

Output of HashMap After Multiple Put and Remove Operations

What is the printed output of the HashMap's internal map after these operations?

DSA Python

class SimpleHashMap:
    def __init__(self):
        self.size = 3
        self.map = [[] for _ in range(self.size)]

    def _get_hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        key_hash = self._get_hash(key)
        bucket = self.map[key_hash]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def remove(self, key):
        key_hash = self._get_hash(key)
        bucket = self.map[key_hash]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return True
        return False

    def __str__(self):
        result = []
        for i, bucket in enumerate(self.map):
            items = ' -> '.join(f'{k}:{v}' for k, v in bucket)
            result.append(f'{i}: {items if items else "null"}')
        return '\n'.join(result)

hm = SimpleHashMap()
hm.put('a', 1)
hm.put('b', 2)
hm.put('c', 3)
hm.put('d', 4)
hm.remove('b')
hm.put('a', 5)
print(hm)

A 0: d:4\n1: a:5\n2: c:3

B 0: a:5\n1: d:4\n2: c:3

C 0: d:4\n1: c:3\n2: a:5

D 0: c:3\n1: a:5\n2: d:4

💡 Hint

Check the hash index for each key and the effect of remove and update.

Keys hash to indices: 'a' and 'd' to 1 and 0 respectively, 'b' removed from 1, 'c' at 2. 'a' updated to 5.

🧠 Conceptual

expert

Why Resize a HashMap and How It Affects Performance

Why do we resize a HashMap when the load factor exceeds a threshold, and what is the main effect on performance?

A To compress keys; reduces key size but increases collision probability.

B To save memory by decreasing bucket count; reduces memory usage but slows lookup.

C To sort keys in buckets; improves iteration order but not lookup time.

D To reduce collisions by increasing bucket count; improves average lookup time from O(n) to O(1).

💡 Hint

Think about how bucket count affects collisions and lookup speed.

Resizing increases buckets, lowering collisions and keeping lookup fast (close to O(1)).