Hash table

avg O(1)

A hash table stores values in an array of buckets, choosing the bucket with a hash function (here h(v) = v mod 7). Insert, search, and delete jump straight to bucket h(v) — average O(1) — and when two values land in the same bucket (a collision) they're kept in a small linked chain scanned linearly. Good hashing keeps chains short; this is how dictionaries and sets are built.

Hash table
Press ▶ to run
Edit the input and press Play

How it works

  1. Compute the bucket index with the hash function h(v).
  2. Insert appends v to that bucket's chain (skipping duplicates).
  3. Search and delete scan only that bucket's chain.
  4. Collisions (same bucket) chain together — keep them short for O(1).

Pseudocode

1h(v) = v mod m                      # m buckets, here 723insert(v): add v to the chain at bucket h(v)   # avg O(1)4search(v): scan the chain at bucket h(v)5delete(v): unlink v from the chain at bucket h(v)6# collisions share a bucket as a linked chain