在 Python 词典中， ( (j*5)+1 ) % 2**i 如何循环遍历所有 2**i
In Python Dictionaries, how does ( (j*5)+1 ) % 2**i cycle through all 2**i
我正在研究 python 如何实现字典。 python 字典实现中的方程之一涉及使用方程
对空字典槽的伪随机探测
j = ((j*5) + 1) % 2**i
其中有解释 here。
这个问题我看了，How are Python's Built In Dictionaries Implemented?，基本明白了字典是怎么实现的
我不明白的是why/how等式：
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) 两者都陷入较小的周期。
我希望能对此有一个更直观的理解，而不是 这个等式很管用，这就是他们使用它的原因。
正如 Jasper 所暗示的，这与伪随机数生成器使用的原理相同，即 linear congruential generators。线性同余生成器是遵循关系 X_(n+1) = (a * X_n + c) mod m 的序列。来自维基页面，
The period of a general LCG is at most m, and for some choices of factor a much less than that. The LCG will have a full period for all seed values if and only if:
m and c are relatively prime.a - 1 is divisible by all prime factors of m.a - 1 is divisible by 4 if m is divisible by 4.
很明显5是满足这些要求的最小的a，即
- 2^i 和 1 互质
- 4 能被 2 整除。
- 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 页的 the original Hull-Dobell paper 中找到这三个条件的证明，以及其他一些可能感兴趣的 PRNG 相关定理。
我正在研究 python 如何实现字典。 python 字典实现中的方程之一涉及使用方程
对空字典槽的伪随机探测j = ((j*5) + 1) % 2**i
其中有解释 here。
这个问题我看了，How are Python's Built In Dictionaries Implemented?，基本明白了字典是怎么实现的
我不明白的是why/how等式：
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) 两者都陷入较小的周期。
我希望能对此有一个更直观的理解，而不是 这个等式很管用，这就是他们使用它的原因。
正如 Jasper 所暗示的，这与伪随机数生成器使用的原理相同，即 linear congruential generators。线性同余生成器是遵循关系 X_(n+1) = (a * X_n + c) mod m 的序列。来自维基页面，
The period of a general LCG is at most m, and for some choices of factor a much less than that. The LCG will have a full period for all seed values if and only if:
mandcare relatively prime.a - 1is divisible by all prime factors ofm.a - 1is divisible by 4 ifmis divisible by4.
很明显5是满足这些要求的最小的a，即
- 2^i 和 1 互质
- 4 能被 2 整除。
- 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 页的 the original Hull-Dobell paper 中找到这三个条件的证明，以及其他一些可能感兴趣的 PRNG 相关定理。