Hashing

Finding items in constant expected time: hash functions, collision resolution by chaining and open addressing, how production hash tables are engineered and attacked, and the probabilistic structures that trade exactness for space.

This part builds on Linear structures.

1 of 3 topics ready, listed in reading order

Hash tablesHash functions, separate chaining, linear and quadratic probing, double hashing, deletion with tombstones, load factor and resizing.Ready

Hashing in practiceHow Python's dict and set work, universal hashing, hash flooding attacks, and cuckoo and Robin Hood hashing.Planned

Probabilistic data structuresBloom filters, count-min sketches and HyperLogLog, with their error rates derived and measured.Planned