Algorithm Guidecomplexity: Avg O(1)

Hash Table

Maps keys to bucket indices with a hash function to store and look up in average O(1). When different keys collide into the same bucket, it resolves them with chaining (linked lists) or open addressing.

01Hash Table

Explore How It Works

Hash table. A hash function (here key % 5) computes the key's bucket number.

put(10) · 10 % 5 = 0. Put 10 in bucket 0.

put(24) · 24 % 5 = 4. Put 24 in bucket 4.

put(14) · 14 % 5 = 4. Collision in bucket 4, which already holds 24 — chain 14 after 24.

put(3) · 3 % 5 = 3. Put 3 in the empty bucket 3.

get(14) · Jump straight to bucket 14 % 5 = 4. Scan the chain: 24 (no) → 14 (match) is found.

The bucket number is computed in one step, so average O(1). Collisions are resolved by chaining, with only a short search inside that bucket.

0›

—

1›

—

2›

—

3›

—

4›

—

Live Python

1def _index(key):

2 return key % capacity # hash → bucket index

4def put(key):

5 i = _index(key)

6 buckets[i].append(key) # on collision, add to chain

8def get(key):

9 i = _index(key)

10 for k in buckets[i]: # linear scan of that bucket only

11 if k == key:

12 return k

13 return None

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

A hash function turns the key into a slot number, so insertion and lookup go directly to that slot. Collisions are resolved within the slot.

💡In Plain Words

Computes the storage location straight from the key.

No searching — it finds items almost instantly (average O(1)).

When cells collide, it chains them together.

📍Where It's Used

–Dictionaries/maps
–duplicate checks
–database indexes
–caches

03 Python Implementation

A clean, readable reference implementation of the core logic of Hash Table.

core_implementation.py

class HashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return None