Space/Time Trade-offs in Hash Coding with…

Bloom's paper asks how a compact in-memory screen can reject missing keys before an expensive exact lookup. Read it to see why one zero bit proves absence, why all-one evidence means only possibly present, and how shared hash positions trade memory for a controlled false-positive path.

Reading focus: How each inserted key sets several shared bit positions and a query replays the same address rule. Why any zero proves a key absent while collisions can make a never-inserted key appear possibly present. How bit occupancy, hash count, exact confirmation, and the cost of false positives determine whether the filter helps.

Communications of the ACM, 1970. Burton H. Bloom. 30 min read, easy difficulty.