SALT Systems LabOverview
Zombie Hashing is a linear probing scheme that keeps performance consistent and data locality high, even at high load factors. Linear probing tables use tombstones (deletion markers) to speed up operations and reduce primary clustering. Those tombstones must be redistributed periodically, which halts all operations and makes performance uneven.
Zombie Hashing redistributes tombstones within small windows instead, so the table never needs to stop. It comes in two variants: an ordered compact table and an unordered vectorized table based on Abseil.
Key features
No global rebuilds
Tombstones are redistributed locally, so operations never stop.
Two variants
An ordered compact linear probing table and an unordered vectorized table built on Abseil.
High load factors
Evaluated at 75%, 85%, and 95% load under churn.
Churn benchmarks
Measures both throughput and latency against RobinHood, Graveyard, Iceberg, CLHT, and Abseil.
Quick start
git clone https://github.com/saltsystemslab/ZombieHT && cd ZombieHT
./setup.sh
./run_throughput.sh # churn throughput experiments
./run_latency.sh # churn latency experiments
./plot_data.sh # report at ./bench/report/main.pdf