A hash table turns a key into a bucket index with a hash function. With a suitable hash and load factor, lookup is O(1) on average, but different keys can map to the same bucket and cause collisions.
A seven-bucket hash-table simulator for insertion, lookup, and collision handling
1. Choose a collision strategy
2. Insert or find a key
Keys such as cat, act, and tac have the same sum of character codes and therefore collide in this example. Load the collision example to insert five such keys.
Hash function
This example sums character codes and takes the remainder modulo the bucket count. It is simple but ignores character order, causing frequent collisions. Practical hash functions mix the positions and values of characters to distribute keys more evenly.
Two ways to handle collisions
Chaining stores a list at each bucket. Multiple keys can share a bucket, but a long chain requires a linear scan.
Linear probing searches consecutive slots until finding an empty one. Lookup follows the same path and stops at an empty slot. Clustering degrades performance as the table fills; implementations often resize before a load factor around 0.7, depending on the design.