Hash Table Explained with Examples

By Khaled Md Tuhidul Hossain · 2026-02-08 · Algorithms

You use hash tables constantly, probably without thinking about it. Python's dict, JavaScript's objects, Java's HashMap. They're all hash tables under the hood, and they're fast. Really fast. O(1) average time for inserts and lookups.

But how do you go from a key like "alice" to a specific slot in an array? And what happens when two different keys want the same slot? That's what we're going to work through.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: hash-table
input: {"keys": ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"], "size": 7}
speed: 600

How a Hash Table Works

A hash table has two main parts: an array (the actual storage) and a hash function (the thing that converts keys into indices).

The hash function takes a key, crunches some math on it, and spits out an index. You store the value at that index. When you want to look it up later, you hash the key again, get the same index, and grab the value directly. No scanning, no searching.

Inserting Key-Value Pairs

Let's walk through inserting a few entries into a hash table of size 7.

We'll use a simple hash: sum the character codes of the key, then mod by the table size.

Insert ("alice", 85):

• hash("alice") = (97+108+105+99+101) % 7 = 510 % 7 = 6
• Store at index 6.

Insert ("bob", 92):

• hash("bob") = (98+111+98) % 7 = 307 % 7 = 6
• Index 6 is taken. We have a collision.

Now what? This is where collision handling comes in.

Handling Collisions

There are two common strategies. Both work, and the choice depends on your situation.

Strategy 1: Chaining

Each slot holds a linked list instead of a single entry. When two keys hash to the same index, you just append to the list.

To look up "bob", you hash it, land on index 6, then walk the short list until you find the matching key. As long as your hash function distributes keys evenly, these lists stay short.

Strategy 2: Open Addressing (Linear Probing)

Instead of lists, you just look for the next empty slot.

So "alice" hashes to 6 and gets placed. "bob" also hashes to 6, finds it occupied, checks 0 (wrapping around), finds it occupied, checks 1, and sits there. During lookup, you follow the same probing sequence until you find the key or hit an empty slot.

Linear probing is cache-friendly since you're accessing consecutive memory, but it can cause clustering where occupied slots bunch together.

Step-by-Step: Building a Hash Table

Let's insert these student scores: alice=85, bob=92, charlie=78, dave=88, eve=95.

Using chaining with table size 7:

After all inserts, the table looks like this:

[0] -> empty
[1] -> dave: 88
[2] -> empty
[3] -> empty
[4] -> charlie: 78
[5] -> empty
[6] -> alice: 85 -> bob: 92 -> eve: 95

Index 6 has three entries chained together. That's not ideal, but lookups there still only take 3 comparisons. A better hash function or a larger table would spread things out more.

Python Implementation

class HashTable:
    def __init__(self, size=16):
        self.size = size
        self.count = 0
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        # Python's built-in hash works well in practice.
        # We just need to map it to a valid index.
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]

        # Update if key already exists
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))
        self.count += 1

        # Resize if load factor exceeds 0.75
        if self.count / self.size > 0.75:
            self._resize()

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]

        for k, v in bucket:
            if k == key:
                return v

        raise KeyError(f"Key '{key}' not found")

    def delete(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return v

        raise KeyError(f"Key '{key}' not found")

    def _resize(self):
        old_buckets = self.buckets
        self.size *= 2
        self.count = 0
        self.buckets = [[] for _ in range(self.size)]

        for bucket in old_buckets:
            for key, value in bucket:
                self.insert(key, value)

    def __contains__(self, key):
        try:
            self.get(key)
            return True
        except KeyError:
            return False

    def __repr__(self):
        items = []
        for bucket in self.buckets:
            for k, v in bucket:
                items.append(f"{k}: {v}")
        return "{" + ", ".join(items) + "}"


# Try it out
ht = HashTable(size=7)
ht.insert("alice", 85)
ht.insert("bob", 92)
ht.insert("charlie", 78)
ht.insert("dave", 88)
ht.insert("eve", 95)

print(ht.get("alice"))      # 85
print(ht.get("charlie"))    # 78
print("bob" in ht)          # True
print("frank" in ht)        # False

ht.delete("bob")
print("bob" in ht)          # False
print(ht)

Notice the _resize method. When the table gets too full (load factor above 0.75), we double the size and rehash everything. This keeps the chains short and lookups fast. It's an O(n) operation, but it happens infrequently enough that the amortized cost of insertion stays O(1).

Time and Space Complexity

The worst case happens when every key hashes to the same index. That turns your hash table into a linked list. In practice, with a decent hash function and resizing, you'll almost always get O(1) performance.

Real Problems Where Hash Tables Shine

Caching. Web servers cache responses keyed by URL. When a request comes in, the server checks the hash table first. If the URL is there, it returns the cached response instantly instead of regenerating it.

Duplicate detection. Need to check if you've seen an element before? Throw it in a hash set. Checking membership is O(1). This comes up constantly in data processing pipelines where you need to deduplicate millions of records.

Frequency counting. Counting word occurrences in a document, tallying votes, tracking how many times each error code appears in your logs. Hash tables make this trivial:

def count_frequencies(items):
    freq = {}
    for item in items:
        freq[item] = freq.get(item, 0) + 1
    return freq

words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
print(count_frequencies(words))
# {'apple': 3, 'banana': 2, 'cherry': 1}

The Two-Sum problem. This is a classic interview question. Given an array and a target sum, find two numbers that add up to it. The brute force approach checks every pair in O(n^2). With a hash table, you do it in one pass:

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]

For each number, you calculate what its partner would need to be, then check if you've already seen that partner. The hash table lookup is O(1), so the whole thing runs in O(n). That's a huge improvement.

Load Factor and Why It Matters

The load factor is simply number_of_entries / table_size. As it grows, collisions become more frequent and performance degrades.

Most implementations resize when the load factor hits 0.7 to 0.8. Python's built-in dict resizes at around 2/3 full. The tradeoff is memory vs speed. A larger table wastes some space but keeps lookups fast.

Here's the thing. If you know roughly how many entries you'll have, you can set the initial size accordingly and avoid resizing entirely. That's a small optimization, but it matters when you're processing millions of entries.

Quick Recap

Hash tables trade a bit of extra memory for blazing fast lookups. The hash function maps keys to indices, and collision handling (chaining or probing) deals with the inevitable overlaps. Keep the load factor reasonable, use a good hash function, and you'll get O(1) performance for inserts, lookups, and deletes.

They're the go-to data structure whenever you need to associate keys with values or check membership quickly. If you find yourself reaching for a nested loop to search for something, stop and ask if a hash table could do it in one pass instead.