Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Compute the bucket index from the key — here, the remainder after dividing by the table size.
  2. If the bucket is empty, the key goes straight in.
  3. If something is already there, the keys collided; chain the new one onto the list.
  4. To look a key up, hash it again and go to that one bucket.
  5. Scan only that bucket — every other bucket is irrelevant by construction.
  6. The longest chain is what a worst-case lookup costs.

Key concepts

  • The hash function decides the distribution, and so the performance
  • Collisions are normal, not a failure
  • Chaining keeps a list per bucket; open addressing probes for another slot instead
  • A prime table size avoids the clustering a composite one causes

When to use it

Whenever you need lookup by key and do not need the keys in order. If you need ordering or range queries, use a search tree.

Did you know

A hash table degrades to a linked list if every key collides — which is why hash functions used on untrusted input have to be unpredictable.