CS With NehalCS With Nehal

Hash Table Simulator

Hash keys into a table and resolve collisions with separate chaining, linear probing or quadratic probing, step by step.

Table settings

Table loaded with 15, 22 and 8. Notice 15, 22 and 8 all hash to 1.

Hash table

0
empty
1
15
2
22
3
8
4
empty
5
empty
6
empty
3
Items stored
0.43
Load factor
items ÷ size
With open addressing, every item lives in the table itself. As the load factor rises, clusters form and probes get longer. Tables are usually resized past about 0.7.

Probe sequence

h, h+1, h+2, h+3, … (mod size)

About This Simulation

This hash table simulator stores keys in a table using a hash function and shows how collisions are resolved. You can compare separate chaining, linear probing and quadratic probing, step through every probe, delete with tombstones and watch the load factor change.

Features

  • MOD hash function for numbers and ASCII-sum hashing for text
  • Separate chaining, linear probing and quadratic probing
  • Insert, search and delete with each probe highlighted
  • Deleted markers (tombstones) for open addressing
  • Table sizes from 5 to 13 and a live load factor

Topics covered

  • Hashing
  • Hash Functions
  • Collisions
  • Separate Chaining
  • Open Addressing
  • Load Factor

Explanation

A hash table stores key–value pairs in an array. A hash function turns each key into an index, so a key can be found directly instead of searching the whole table. When two keys hash to the same index, a collision occurs and must be resolved.

How it works

  1. Hash the key, for example index = key MOD table size.
  2. Separate chaining: each slot holds a linked list, and colliding keys are added to the list at that slot.
  3. Linear probing: if the slot is full, try the next slot (h + 1, h + 2, …), wrapping around to the start.
  4. Quadratic probing: try h + 1², h + 2², h + 3², …, which spreads keys out and reduces clustering.
  5. With open addressing, deleted slots are marked as deleted rather than emptied, so searches don't stop too early.
  6. Load factor = items ÷ table size. As it rises, collisions increase, so tables are resized when it passes about 0.7.

Why it matters

Hash tables give average O(1) insertion and lookup, which is why they power dictionaries in Python, HashMap in Java, database indexes, caches and symbol tables in compilers. Hashing is on the A Level syllabus and in CSE220.

Frequently Asked Questions

What is a collision in a hash table?

When two different keys produce the same index from the hash function.

Which is better, chaining or open addressing?

Chaining handles high load factors gracefully and makes deletion simple. Open addressing uses less memory and is more cache-friendly but slows down sharply as the table fills.

Why use a prime number as the table size?

A prime size spreads keys more evenly with MOD hashing and guarantees that quadratic probing can reach enough slots when the table is less than half full.

What makes a good hash function?

It is fast to compute, always gives the same index for the same key and spreads keys evenly across the table.

Related Simulations

Data Structures

Linked List Simulator

Insert, delete and search in a linked list stored in arrays, with the start and free pointers and every pointer change shown step by step.

Algorithms

Searching Algorithms

Run linear, binary, ternary and quaternary search on your own array and step through the code one line at a time.

Data Structures

Binary Search Tree Simulator

Insert, search and delete in a binary search tree step by step, including all three deletion cases and the in-order successor.

Data Structures

B+ Tree

Insert, delete, search in a B+ tree visualiser