HashMap Implementation from Scratch in DSA Python - Time & Space Complexity

Time Complexity: HashMap Implementation from Scratch

O(n) worst case, O(1) average case

Understanding Time Complexity

When building a HashMap from scratch, it's important to understand how fast it can add, find, or remove items.

We want to know how the time to do these actions changes as we store more items.

Scenario Under Consideration

Analyze the time complexity of the following simple HashMap put operation.

class SimpleHashMap:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        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 stores key-value pairs in buckets using a hash function and handles collisions by storing multiple pairs in a list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the bucket list to find if the key exists.
• How many times: Up to the number of items in that bucket, which depends on how many keys hash to the same index.

How Execution Grows With Input

As more items are added, buckets may hold more pairs, making the search inside a bucket longer.

Input Size (n)	Approx. Operations
10	About 1 to 2 checks per put (few collisions)
100	About 5 to 10 checks per put (more collisions)
1000	About 50 to 100 checks per put (many collisions)

Pattern observation: Without resizing, the time grows roughly proportional to the number of items per bucket, which grows as total items increase.

Final Time Complexity

Time Complexity: O(n) in worst case, O(1) on average

This means usually adding or updating a key is very fast, but if many keys collide, it can slow down linearly with the number of items.

Common Mistake

[X] Wrong: "HashMap operations always take the same constant time no matter what."

[OK] Correct: If many keys end up in the same bucket, the code must check each one, making the operation slower.

Interview Connect

Understanding how collisions affect speed shows you know the real behavior of hash maps, a key skill for coding interviews.

Self-Check

"What if we resize and rehash the buckets when they get too full? How would the time complexity change then?"