Tag
open-addressing
- May 18, 2026 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. data structures
- Aug 31, 2025 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. data structures
- Jun 29, 2025 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. data structures
- Oct 2, 2024 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. data structures
- Aug 9, 2024 Probe Sequences in Open-Addressed Hash Tables How linear, quadratic and double hashing differ in clustering behaviour, why deletion needs tombstones or backward shifting, and what Robin Hood ordering buys. algorithms
- Jul 31, 2024 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. data structures
- Aug 18, 2023 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. data structures