So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algo...

There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen)

I am a big fan of http://www.amazon.com/Probability-Computing-Randomized-Algor... . Every time it teaches a new chunk of theory it motivates and grounds it in some algorithmic application.

If you want to learn more about this sort of thing there is an excellent textbook which teaches probability theory using randomised algorithms (eg uniform hashing, load balancing, queueing theory etc).

http://www.amazon.com/Probability-Computing-Randomized-Algor...

It's one of my favourite textbooks and it's full of powerful methods and intuitions for any programmer.

NINJA EDIT PLUG: If anyone wants to work through that book I would be more than happy to help out and answer questions ([email protected]). I wouldn't mind a refresher myself and I've always found that explaining things to other people helps clarify my own thinking.

> Am I missing something?

No, I was confused too. The maths doesn't make sense to me and the whole blog seems to exist just to push amazon affiliate links.

If you are actually interested in probability theory, I highly recommend this (non-affiliate-link) book:

http://www.amazon.co.uk/Probability-Computing-Randomized-Alg...

It does a good job of motivating the subject by applying the new theory in each chapter to the study of useful randomized algorithms.