[解決済み] ハッシュのランダム化を有効にすると、なぜ tuple(set([1, "a", "b", "c", "z", "f"]) == tuple(set(["a", "b", "c", "z", "f",1])) 85% of times なのですか?

質問

別の質問に対するジブン・ゼロ・ピレアスの回答 ということになります。

x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)

プリント True で約85%の確率で ハッシュランダム化 を有効にしています。なぜ 85% なのか？

どのように解決するのですか？

この質問を読んでいる人は、両方を読んでいると仮定します。

• ゼロ・ピレウス社の回答 と

• CPythonの辞書についての説明です。 .

まず注意すべきは、ハッシュのランダム化はインタプリタ起動時に決定されることです。

各文字のハッシュは両方のセットで同じになるので、問題になり得るのは衝突があった場合だけです（ここで順番が影響されます）。

2 番目のリンクの推論により、これらのセットのバック配列は長さ 8 で開始することがわかります。

_ _ _ _ _ _ _ _

最初のケースでは 1 :

_ 1 _ _ _ _ _ _

と入力し、残りを挿入します。

α 1 ? ? ? ? ? ?

その後、サイズ32にリハッシュされます。

    1 can't collide with α as α is an even hash
  ↓ so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

の場合、残りを挿入します。

? β ? ? ? ? ? ?

そして、1を挿入してみる。

    Try to insert 1 here, but will
  ↓ be rehashed if β exists
? β ? ? ? ? ? ?

そして、蒸し返される。

    Try to insert 1 here, but will
    be rehashed if β exists and has
  ↓ not rehashed somewhere else
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

つまり、反復の順序が異なるかどうかは、βが存在するかどうかだけに依存します。

βが存在する確率は、5つの文字のどれかが8モジュールの1にハッシュ化する確率です。 と は1モジュロ32にハッシュします。

1 modulo 32 にハッシュするものはすべて 1 modulo 8 にもハッシュするので、32 個のスロットのうち、5 つのうちの 1 つがスロット 1 にある確率を見つけたいのです。

5 (number of letters) / 32 (number of slots)

5/32は0.15625なので 2つのセット構成の間で順序が異なる確率は15.625%¹である。 .

まったく不思議なことに、これはまさにゼロ・ピレウスが測定したものです。

_{技術的には、これさえも明らかではありません。5 つのハッシュのすべてがリハッシュのために一意であるように装うことができますが、線形プロービングのため、実際には "束ねられた構造が発生しやすくなります...しかし、単一のスロットが占有されているかどうかにのみ注目しているので、これは実際には影響を与えません。}