Hash tables

At a glance

A hash table maps a key to a bucket or slot. A suitable hash function helps distribute keys evenly. Typical lookup, insertion and deletion costs are O(1) on average, but collisions and resizing affect performance.

Hash functions and buckets

A hash table uses a hash function to decide where to store an item. In this exercise, a simple modulus operation maps an ID to one of several buckets.

Interactive bucket simulator

INTERACTIVE / LIVE

Build a hash table

Change the bucket count, add your own IDs and watch collisions appear.

Live demo

Collision strategy

Show the C# logic behind this step

Challenge: can you predict a bucket?

Compute 19 % 5 by hand. Why would searching for 29 begin at the same bucket but potentially fail?

Reveal explanation

Answer: both 19 and 29 have remainder 4. Hashing identifies candidates, but does not prove the key exists.

What happens during a collision?

A collision occurs when different keys map to the same bucket. Collisions are normal; they must be handled correctly. Common approaches include separate chaining and open addressing.

A simple illustration of a hash table with entries mapped into buckets

Complexity

Operation	Average case	Worst case
Lookup	`O(1)`	`O(n)`
Insert	`O(1)`	`O(n)`
Delete	`O(1)`	`O(n)`

Two ways to handle collisions

Separate chaining stores multiple entries at the same bucket, often in a list or similar collection. Open addressing searches for a different available slot in the table. Both need to check keys for equality after hashing.

Load factor and resizing

A table with many stored keys relative to its number of buckets has a high load factor. More collisions become likely, so implementations often increase capacity and redistribute existing entries. Resizing is expensive when it happens, even if ordinary operations are fast on average.

Language examples

var ages = new Dictionary<string, int>();
ages["Alex"] = 24;
if (ages.TryGetValue("Alex", out int age))
    Console.WriteLine(age);

#include <unordered_map>
#include <string>
#include <iostream>
std::unordered_map<std::string, int> ages;
ages["Alex"] = 24;
if (auto it = ages.find("Alex"); it != ages.end())
    std::cout << it->second << '\n';

Equality is part of hashing

A hash code chooses a candidate bucket, but it does not prove that two keys are equal. A correct hash table checks key equality after locating candidates. Equal keys must produce equal hash codes under the chosen equality rules, while unequal keys are allowed to collide.

What resizing changes

As more items enter the table, average bucket occupancy tends to rise. A typical implementation allocates a larger bucket array and reassigns existing keys to new buckets. That operation can take O(n) at the moment it happens, even when average insertion cost over many operations is constant.

Practical key design

Avoid mutable key fields that affect equality or hash codes while the key is stored. If a dictionary’s key changes without the table being updated, future lookups can fail. Prefer stable value objects or strings for identifiers.

Go deeper: implement the actual data structure

Start with the bucket calculation and equality rules, then work through collisions, reusable code, deletion and resizing. Try the simulator above before reading the implementation.