“Esoteric Data Structures and Where to Find Them”
summary
Describes four concrete tools and their trade-offs: slot map gives true constant-time insert/lookup/erase using a generation counter plus free list to avoid ABA and packs elements contiguously (proposal in SG14); bloom filter stores M bits with K cheap hashes to get constant-time queries and tunable false-positive rate P but no deletes; navigation mesh (Recast common) cuts node count in examples from ~370→16 and path steps 17→3; hash pointer enables tamper detection (blockchain O(N), Merkle tree O(log N)).
AI-written summary · about
chapters (19)
- 0:00Introduction
- 0:36What is a slot map?
- 1:44Slot map mechanics
- 3:25Slot map vs alternatives
- 4:30Inserting into a slot map
- 6:06Erasing from a slot map
- 7:15Slot map trade-offs
- 8:01Slot map variations
- 10:03Introduction to bloom filters
- 12:36Bloom filter mechanics
- 13:52Probabilistic lookups
- 15:41Tuning bloom filters
- 16:44Navigation mesh basics
- 17:07Nav mesh representations
- 20:03Introduction to hash pointers
- 20:58Blockchain technology
- 21:55Tamper detection mechanics
- 24:08Merkle trees and conclusions
- 25:37Q&A session
related talks
04mThe Slot Map Data Structure
01h 04mBetter Code: Data Structures
40mImmutable Data Structures in C++
54mAbseil's Open Source Hashtables: 2 Years In
51m“Cache Optimized Hash Tables”
55mAbusing Your Memory Model for Fun and Profit
49mMy favorite (constexpr) data structures
55m “High Performance C++ Concurrent Transactional Data Structures"