2

ハッシュテーブルのチュートリアルで線形プローブについて読んでいて、これに出くわしました：

線形プロービングでは、ステップ サイズはほとんど常に 1 ですが、最終的にすべてのインデックスがアクセスされるように、ステップ サイズがテーブル サイズに対して相対的に素数である限り、他のステップ サイズを使用してもかまいません。この制限が満たされない場合、すべてのインデックスにアクセスできない可能性があります...

(基本的な問題は次のとおりです。配列内のすべてのインデックスを任意のインデックスから開始し、一定数のインデックスをスキップして次のインデックスに移動し、必要に応じてモジュロで配列の先頭にラップする必要があります。)

ステップ サイズがテーブル サイズに対して相対的に素でない場合、すべてのインデックスを参照できない理由は理解できますが、逆が真である理由がわかりません。ステップ サイズが相対的に素である場合、すべてのインデックスが参照されるということです。配列サイズ。

この比較的主要なプロパティが、手動で作成したいくつかの例で機能することを確認しましたが、すべての場合に機能する理由はわかりません。

要するに、私の質問は次のとおりです。配列のすべてのインデックスが、配列サイズに比較的素なステップでアクセスされるのはなぜですか? これの証拠はありますか？

ありがとう！

4

2 に答える 2

3

巡回群に関するウィキペディア

環 Z/nZ の単位は、n と互いに素な数です。

また：

[2つの数が互いに素な場合] ax + by = 1 となる整数 x と y が存在する

したがって、「a」が歩幅で「b」が配列の長さである場合、次の方法で任意のインデックス「z」に到達できます。

axz + byz = z

=>

axz = z (mod b)

つまり、「xz」回ステップします (および配列を「yz」回ラップします)。

于 2012-07-30T08:11:34.647 に答える
1

ステップ数lcm(A,P)/PまたはA/gcd(A,P)はA配列サイズで、Pはこの魔法の余素です。

したがって、次の場合gcd(A,P) != 1、ステップ数は次の値よりも少なくなります。A
反対に、gcd(A,P) == 1(coprimes) の場合、ステップ数は A になり、すべてのインデックスがアクセスされます。

于 2012-07-31T00:20:25.393 に答える