Labs / Computer Science
Hash Table
Every key is run through a hash function that picks a bucket, then dropped in. When two keys pick the same bucket they collide and hang off the same chain. Insert keys, resize the table, or swap in a worse hash function and watch the chains grow.
items 0α 0.00longest 0collisions 0
What to try
- As the load factor α climbs past 1.0, what happens to the length of the longest chain?
- Switch to the "Worst" hash function. Where do all the keys go, and why is that the slowest possible table?
- Fill the table, then press Rehash ×2. Why do the chains suddenly get shorter even though no keys were removed?
- With a fixed number of keys, does doubling the buckets ever reduce collisions all the way to zero? What would that require?
- Compare "Even spread" and "Poor" at the same load factor — which one keeps lookups fast, and how can you tell from the picture?