Why Hash Map Exists and What Problem It Solves in DSA Python - Why This Pattern

Mental Model

A hash map helps us find things quickly by using a special code to jump directly to where the item is stored.

Analogy: Imagine a huge library where books are scattered randomly. Without a system, you must check every shelf to find a book. A hash map is like having a special code on each book that tells you exactly which shelf and spot to look at, so you find it instantly.

Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   ?   ?   ?   ?   ?   ?   ?

Without hash map:
Search: Book -> Check shelf 1 -> Check shelf 2 -> ... -> Check shelf n

With hash map:
Key -> Hash function -> Index -> Direct access to shelf

Dry Run Walkthrough

Input: Store and find the value for key 'apple' in a collection of fruits

Goal: Show how hash map lets us find 'apple' quickly without checking all items

Step 1: Calculate hash code for key 'apple' using hash function

Hash code for 'apple' -> 3 (example)
Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Index 3 selected

Why: We need a number to know where to store or find 'apple'

Step 2: Store value 'fruit' at index 3 in the array

Array: [ ] [ ] [ ] ['apple':'fruit'] [ ] [ ] [ ] [ ] [ ] [ ]

Why: Placing 'apple' at index 3 lets us find it directly later

Step 3: To find 'apple', calculate hash code again -> 3

Hash code for 'apple' -> 3
Array: [ ] [ ] [ ] ['apple':'fruit'] [ ] [ ] [ ] [ ] [ ] [ ]

Why: Using the same hash code points us to the right spot

Step 4: Check index 3 and find 'apple' key, return value 'fruit'

'apple':'fruit' found at index 3

Why: We found the value quickly without searching all items

Result:

Array: [ ] [ ] [ ] ['apple':'fruit'] [ ] [ ] [ ] [ ] [ ] [ ]
Found value: fruit

Annotated Code

DSA Python

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

    def _hash(self, key: str) -> int:
        # Simple hash: sum of char codes mod size
        return sum(ord(c) for c in key) % self.size

    def set(self, key: str, value: str) -> None:
        index = self._hash(key)  # get index to store
        self.map[index] = (key, value)  # store key-value pair

    def get(self, key: str) -> str:
        index = self._hash(key)  # get index to find
        pair = self.map[index]
        if pair is None:
            return 'Not found'
        if pair[0] == key:
            return pair[1]  # return value if key matches
        return 'Not found'  # key mismatch means not found

# Driver code
hash_map = HashMap()
hash_map.set('apple', 'fruit')
result = hash_map.get('apple')
print(f'Found value: {result}')

index = self._hash(key) # get index to store

Calculate hash code to find storage index

self.map[index] = (key, value) # store key-value pair

Store the key and value at the computed index

index = self._hash(key) # get index to find

Calculate hash code to find retrieval index

if pair[0] == key:

Check if stored key matches requested key

return pair[1] # return value if key matches

Return the value associated with the key

Output

Found value: fruit

Complexity Analysis

Time: O(1) on average because hash function lets us jump directly to the item without searching

Space: O(n) because we store n items in an array

vs Alternative: Compared to searching a list which is O(n), hash map is much faster for lookups

Edge Cases

Key not present in map

Returns 'Not found' because no value stored at computed index or key mismatch

DSA Python

if pair is None:

Empty map with no items

Returns 'Not found' immediately because array slots are empty

DSA Python

if pair is None:

Collision where two keys hash to same index

Current simple code overwrites previous value, so only last stored key-value remains

DSA Python

self.map[index] = (key, value)  # store key-value pair

When to Use This Pattern

When you need very fast lookup by key and want to avoid searching all items, reach for hash map because it uses a hash function to jump directly to the data.

Common Mistakes

Mistake: Not using a hash function and searching all items linearly
Fix: Implement a hash function to compute index for direct access

Mistake: Ignoring collisions causing data loss
Fix: Use collision handling methods like chaining or open addressing

Summary

Hash map stores key-value pairs for fast lookup using a hash function.

Use hash maps when you want quick access to data by keys without searching everything.

The key insight is using a hash function to convert keys into direct array indexes for instant access.