Probabilistic Data Structures

on YouTube ↗29m

" summary

Go code implements a bloom filter (bitfield with k hashes, references to murmur3 and chat 256) and a cuckoo filter (fingerprints, buckets, SHA1-derived hashes). Bloom example uses one-bit-per-position, shows the false-positive vs. zero false-negative property and gives the error formula; implementation fits ~50 lines. Cuckoo supports deletions, relocates entries until a retry limit, panics on full table, and claims better space/perf at ~95% utilization. Slides and code links provided.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:52A primer: storing unique usernames
3. 3:58Probabilistic structures
4. 5:15Bloom Filter
5. 6:07Use cases
6. 7:57How do they work
7. 9:25Reading
8. 10:51possible issues Hash Collision
9. 11:18Solutions?
10. 13:32Accuracy
11. 14:21Code time
12. 15:51Safe filter
13. 17:11Cuckoo Filters
14. 18:43Some terminology
15. 19:39Relocating
16. 24:07Inserting - without conflict
17. 25:13Shuffling elements
18. 26:52Lookup
19. 27:50Delete fingerprint
20. 28:25Did not make the cut