python - 在 Python 字典中， ( (j*5)+1 ) % 2**i 如何循环遍历所有 2**i

Question

我正在研究 python 如何实现字典。python字典实现中的一个等式与使用等式对空字典槽的伪随机探测有关

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

这是解释here。

我读过这个问题，Python 的内置字典是如何实现的？，并且基本了解字典是如何实现的。

我不明白的是为什么/如何等式：

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

循环遍历 的所有剩余部分 2**i。例如，如果i = 3总起始大小为 8. j经历循环：

0
1
6
7
4
5
2
3
0

如果起始大小是 16，它将经历循环：

0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3 0

这对于探测字典中的所有插槽非常有用。 但为什么它会起作用？ 为什么会 j = ((j*5)+1)起作用但不起作用j = ((j*6)+1) 或j = ((j*3)+1) 两者都卡在较小的周期中。

我希望能更直观地理解这一点，而不是等式有效，这就是他们使用它的原因。

Answer 1

正如 Jasper 所暗示的，这与伪随机数生成器使用的原理相同，即线性同余生成器。一个线性同余生成器是一个遵循关系的序列X_(n+1) = (a * X_n + c) mod m。从维基页面，

一般 LCG 的周期最多为 m，而对于因子 a 的某些选择则要小得多。当且仅当：

1. m并且c是相对优质的。
2. a - 1能被 的所有素因数整除m。
3. a - 1如果能被 整除，则能被 4m整除4。

很明显，5 是a满足这些要求的最小值，即

1. 2^i 和 1 互质。
2. 4 能被 2 整除。
3. 4 能被 4 整除。

同样有趣的是，5 并不是唯一满足这些条件的数字。9也可以。取m为 16，使用j=(9*j+1)%16产量

0 1 10 11 4 5 14 15 8 9 2 3 12 13 6 7

这三个条件的证明可以在第 5 页的原始 Hull-Dobell 论文中找到，以及其他一些可能感兴趣的 PRNG 相关定理。