How hashing is used to estimate size of sets (opens in new tab)

If you think “hashing is just for lookups”, then this post is your red pill. This two-part series explores how hashing is used beyond hashmaps - in settings where randomness and probabilistic reasoning are the real heroes. In this first part, we will see 2 examples where hashing is used to simulate uniformity, even when the input is highly structured or biased and helps in estimating the cardinality of sets (even when we can’t list them explicitly) LogLog: Here we are given a huge stream of n...