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

So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402 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 https://www.usenix.org/conference/atc20/presentation/chen)