the.com/bloom filter
a bouncer who can swear you're definitely not on the list, but never swears you are.
means a probabilistic data structure that tests whether an element might be in a set, trading perfect accuracy for tiny memory and instant speed.
from invented in 1970 by burton howard bloom at bell labs, back when computer memory was expensive enough to make exactness a luxury nobody could afford.
false positivespossible, and expected by design
false negativesmathematically impossible, ever
deletioncannot remove items without breaking it
size tradeoffbigger filter, fewer false positives, more memory
for instance
chrome safe browsing — google once used one to flag malicious urls locally, offline
medium usernames — checks if a username is taken before hitting the database
bitcoin spv wallets — used bloom filters to fetch relevant transactions without full blockchain
cassandra database — skips disk reads for keys that definitely do not exist