Python Dictionariesでは、どのように（（j * 5）+1）％2 **すべて2を循環**

Question

私はPythonが辞書をどのように実装しているかを研究しています。 Pythonの辞書の実装における方程式の一つは、hereを説明する方程式

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

を使用して空の辞書スロットのプロービング擬似ランダムに関する。

私はこの質問How are Python's Built In Dictionaries Implementedを読んで、基本的に辞書がどのように実装されているか理解しています。

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

サイクル2**iのすべての余りを経て：私は理解していない何

はなぜ/どのように方程式です。例えば、8 jの総出発サイズがサイクルを通過するためi = 3場合：出発サイズが16であれば

0 
1 
6 
7 
4 
5 
2 
3 
0 

することは、それがサイクルを行く：

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

これは、擬似乱数ジェネレータが使用するのと同じ原則であり、ジャスパーは、linear congruential generatorsを暗示しています。線形合同発生器は、関係X_(n+1) = (a * X_n + c) mod mに続くシーケンスです。 wikiページから、

一般的なLCGの期間は、最大でm、いくつかの要因の選択肢はそれよりはるかに少ないです。 LCGは場合に限り、すべてのシード値の完全な期間を持つことになります。

1. mとcは互いに素です。
2. a - 1は、mのすべての素因数で割り切れる。
3. a - 1は、mが4で割り切れる場合、4で割り切れる。

それはつまり、5はこれらの要件を満たすために最小aであることを確認するために

1. 2 ^私は明らかだと1は互いに素です。
2. 4 2.
3. 4で割り切れることも興味深いことに、5は、これらの条件を満足する数だけではない

4で割り切れます。 9も動作します。これら三つの条件のための証拠はまた、対象となり得る他のPRNG関連定理の束と一緒に、5ページthe original Hull-Dobell paperに見出すことができるj=(9*j+1)%16収率

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

を使用して、16であることがmを取ります。