Skip to content
AITroveRead. Build. Understand.
Reading list

Hashing

Keyed lookup, collisions, and membership.

Keyed lookup, collisions, and membership. Work through the operation contract, runnable case, and cost before selecting the structure for a real workload.

Lessons

Practice and next steps

LRU caches: couple keyed lookup to recency order

Bloom filters: reject absent keys without claiming exact membership

Sparse sets: constant-time membership for bounded integer IDs

Open-addressed hash tables: tombstones and rebuilds

Index snapshots: publish related maps as one in-memory version

Count-min sketches: bounded-memory event estimates

Bitvector rank and select: count and locate set bits

Sorted runs and tombstones: model an LSM read path

Robin Hood hashing: probe distance and backward-shift deletion

Cuckoo hashing: relocate keys and recover from cycles

Inverted indexes: intersect sorted incident postings

Positional postings: find exact token phrases

Trigram indexes: filter and verify substring candidates

Front-coded lexicons: store shared prefixes within sorted term blocks

LFU caches: evict by frequency, then recency

Misra–Gries: find frequent-item candidates in one pass

Space-Saving: ranked candidates with count bounds

HyperLogLog: estimate unique IDs with fixed registers

Counting Bloom filters: delete only a known insertion

Scalable Bloom filters: grow without discarding old members

Blocked Bloom filters: localize probes and watch skew

Cuckoo filters: relocate compact fingerprints safely

Spatial hash grids: move points between occupied cells

Elias–Fano: split sorted IDs into low parts and high bits

Chunked integer sets: switch sparse arrays to dense bitmaps

Gap-encoded postings: add checkpoints to bytewise seeks

Slab slots: reuse fixed-size pages with generation checks

Bitmap hash tries: copy paths for immutable alert maps

Extendible hashing: split buckets through a shared directory

CLOCK caches: revisit pages through reference bits

Segmented LRU: separate probation from protected reuse

Frequency admission: compare an arrival with an eviction victim

Resident LRU-K: Evict by the Kth Recent Reference

Static XOR filters: peel a fingerprint membership index

Linear hashing: split one bucket at a time as a table grows

Two-level perfect hashing: exact static case membership

Block-max postings: skip safe document-score regions

MinHash bands: retrieve incident candidates, then check exact overlap

Run-length bitmaps: union, intersect, and subtract alert spans

Count Sketch: estimate signed incident frequencies with row medians

Hopscotch hashing: keep each shipment near its home bucket

Invertible Bloom tables: peel differences between replica ID sets

SimHash bands: find near-duplicate incident fingerprints

All-one frequency buckets: increment, decrement, and read both extremes

Curriculum

Keyed lookup, collisions, and membership.

  1. 1Hash maps: keyed lookup with collision and load costs
  2. 2Hash sets: fast membership without an order promise
  3. 3LRU caches: couple keyed lookup to recency order
  4. 4Bloom filters: reject absent keys without claiming exact membership
  5. 5Sparse sets: constant-time membership for bounded integer IDs
  6. 6Open-addressed hash tables: tombstones and rebuilds
  7. 7Index snapshots: publish related maps as one in-memory version
  8. 8Count-min sketches: bounded-memory event estimates
  9. 9Bitvector rank and select: count and locate set bits
  10. 10Sorted runs and tombstones: model an LSM read path
  11. 11Robin Hood hashing: probe distance and backward-shift deletion
  12. 12Cuckoo hashing: relocate keys and recover from cycles
  13. 13Inverted indexes: intersect sorted incident postings
  14. 14Positional postings: find exact token phrases
  15. 15Trigram indexes: filter and verify substring candidates
  16. 16Front-coded lexicons: store shared prefixes within sorted term blocks
  17. 17LFU caches: evict by frequency, then recency
  18. 18Misra–Gries: find frequent-item candidates in one pass
  19. 19Space-Saving: ranked candidates with count bounds
  20. 20HyperLogLog: estimate unique IDs with fixed registers
  21. 21Counting Bloom filters: delete only a known insertion
  22. 22Scalable Bloom filters: grow without discarding old members
  23. 23Blocked Bloom filters: localize probes and watch skew
  24. 24Cuckoo filters: relocate compact fingerprints safely
  25. 25Spatial hash grids: move points between occupied cells
  26. 26Elias–Fano: split sorted IDs into low parts and high bits
  27. 27Chunked integer sets: switch sparse arrays to dense bitmaps
  28. 28Gap-encoded postings: add checkpoints to bytewise seeks
  29. 29Slab slots: reuse fixed-size pages with generation checks
  30. 30Bitmap hash tries: copy paths for immutable alert maps
  31. 31Extendible hashing: split buckets through a shared directory
  32. 32CLOCK caches: revisit pages through reference bits
  33. 33Segmented LRU: separate probation from protected reuse
  34. 34Frequency admission: compare an arrival with an eviction victim
  35. 35Resident LRU-K: Evict by the Kth Recent Reference
  36. 36Static XOR filters: peel a fingerprint membership index
  37. 37Linear hashing: split one bucket at a time as a table grows
  38. 38Two-level perfect hashing: exact static case membership
  39. 39Block-max postings: skip safe document-score regions
  40. 40MinHash bands: retrieve incident candidates, then check exact overlap
  41. 41Run-length bitmaps: union, intersect, and subtract alert spans
  42. 42Count Sketch: estimate signed incident frequencies with row medians
  43. 43Hopscotch hashing: keep each shipment near its home bucket
  44. 44Invertible Bloom tables: peel differences between replica ID sets
  45. 45SimHash bands: find near-duplicate incident fingerprints
  46. 46All-one frequency buckets: increment, decrement, and read both extremes
Storage details