Hash Table

#How does it work?

A hash table stores keys by turning them into an array index with a hash function. To find a key you don't scan all the data: you compute the hash and go straight to the right bucket.

Different keys can land in the same bucket; this is a collision. With separate chaining, used in this lesson, each bucket keeps a small list of the keys that land in it.

A good hash function spreads keys evenly across buckets. Chains stay short, so insert, search and remove take constant time on average.

#Try it yourself

#Basic operations

insert(key)

Finds the bucket with hash(key); if the key isn't there, appends it to the chain.

search(key)

Scans only the chain in bucket hash(key).

remove(key)

Finds the key in its bucket's chain and unlinks it.

load factor

Number of elements / number of buckets. Past a limit (e.g. 0.75) the table grows and every key is rehashed.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class HashSet:
    """Separate chaining: each bucket is a list of the keys that hash to it."""

    def __init__(self, bucket_count: int) -> None:
        self.buckets: list[list[int]] = [[] for _ in range(bucket_count)]

    def _hash(self, key: int) -> int:
        return key % len(self.buckets)

    def contains(self, key: int) -> bool:
        return key in self.buckets[self._hash(key)]

    def add(self, key: int) -> None:
        if not self.contains(key):
            self.buckets[self._hash(key)].append(key)

    def remove(self, key: int) -> None:
        chain = self.buckets[self._hash(key)]
        if key in chain:
            chain.remove(key)


s = HashSet(7)
for key in (15, 8, 22, 31):  # 15, 8 and 22 all hash to bucket 1
    s.add(key)

print(str(s.contains(22)).lower())
s.remove(8)
print(str(s.contains(8)).lower())
print(*s.buckets[1])

#Complexity

Average O(1) holds as long as the load factor stays low and the hash function spreads keys well. If every key lands in the same bucket, the table becomes a linked list and operations are O(n). Growing takes O(n) at once but happens rarely, so the cost per element is constant (amortised O(1)).

#When to use it?

Anywhere you need fast access by key: dictionaries and sets (Python dict/set, Java HashMap, JavaScript Map/Set), caches, counters, duplicate checks. If you need to walk elements in order or run range queries, balanced trees fit better.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Rabin-Karp Algorithm