vendredi 22 mai 2020

Hash collision resolution by double hash in Python source code

from https://hg.python.org/cpython/file/52f68c95e025/Objects/dictobject.c#l72

"The first half of collision resolution is to visit table indices via this recurrence:

j = ((5*j) + 1) mod 2**i

For any initial j in range(2**i), repeating that 2**i times generates each int in range(2**i) exactly once (see any text on random-number generation for proof)."

Can somebody direct me to such a proof?

Thanks




Aucun commentaire:

Enregistrer un commentaire