Data Structures · Cluster
Hash Tables
Hashing, collision policy, and open addressing.
- 01 Separate Chaining and the Load-Factor Threshold How a bucket array with per-bucket lists produces expected constant-time lookup, what the load factor controls, and why chained tables keep working above a load of one.
- 02 Open Addressing, Probe Sequences, and the Cost of Deletion Why open-addressed tables store keys in the slot array, how a probe sequence defines lookup, and why deletion requires tombstones or backward shifting.
- 03 Linear Probing and the Arithmetic of Primary Clustering Why probing consecutive slots produces runs of occupied cells, how those runs change the expected probe count, and how backward-shift deletion repairs a probe chain.
- 04 Hash Functions for Table Indexing: Mixing, Avalanche, and Universal Families What a table hash must satisfy beyond producing an integer, why identity hashing fails on power-of-two tables, and how multiply-shift and finalizers repair weak input bits.
- 05 Double Hashing and Quadratic Probing Without Primary Clustering How per-key strides and triangular offsets break the runs that linear probing creates, what each costs in arithmetic, and why the table size must cooperate.
- 06 Incremental Rehashing: Spreading a Resize Across Operations How two tables and a migration cursor turn an O(n) resize pause into constant work per operation, and what lookups must do while both tables are live.
- 07 Robin Hood Hashing and the Distribution of Probe Lengths How equalizing displacement from the home slot bounds the worst probe sequence, why the variance collapses, and what early termination buys on lookups.
- 08 Cuckoo Hashing and the Guarantee of Two Probes How two hash functions and a displacement rule give worst-case constant lookup, why insertion can cycle, and how a stash or a larger bucket count makes it succeed.
- 09 SwissTable Control Bytes and Group-Wise Probing How a one-byte tag per slot lets a lookup reject fifteen candidates with one SIMD comparison, and why metadata separate from keys changes the memory hierarchy.
- 10 Hash Flooding and the Case for Keyed Hash Functions Why a predictable hash lets an attacker collapse a table to a linked list, how SipHash and per-process seeding restore the expected bound, and what the defence costs.