在Python词典中,((j*5)+1)%2**i如何遍历所有2**i

Question

我正在研究python如何实现字典.python字典实现中的一个等式涉及使用等式的空字典时隙的伪随机探测

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

这里解释了.

我已经读过这个问题,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远小于此.当且仅当以下情况时,LCG将对所有种子值有一个完整的期间:

1. m并且c是相对素数.
2. a - 1被所有主要因素整除m.
3. a - 1如果m可被整除,则可被4 整除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相关定理.