Hash table tradeoffs: CPU, memory, and variability

Roman Leventov
Aug 7 · 13 min read

Factor 1: non-memory-related CPU cost of a key search or an insertion

Factor 2: memory

Linear memory footprint by tiers

The number of locations accessed in each memory tier during a key search or an insertion

The relative locality of random accesses to the memory tiers

Other memory-related subfactors

Factor 3: variability

External factors

Examples of tradeoffs between the factors

Low vs. high maximum load factor

Linear vs. quadratic probing vs. double hashing

Quadratic probing vs. Robin Hood hashing

Inline entries vs. separately allocated nodes

Open addressing vs. separate chaining

SwissTable vs. F14

Roman Leventov

Written by

Software engineer and designer, author. timeandspace.io

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade