[解決済み] なぜ、ハッシュを組み合わせるのにXORがデフォルトなのですか?
2022-04-24 19:35:02
質問
2つのハッシュがあるとする
H(A)
と
H(B)
で、それらを結合したいとします。2つのハッシュを結合する良い方法は、次のようなものだと読んだことがあります。
XOR
を、例えば
XOR( H(A), H(B) )
.
私が見つけた最も良い説明は、このページで簡単に触れています。 ハッシュ関数ガイドライン :
ほぼランダムに分布する2つの数値をXORすると、やはりほぼランダムに分布する*が、今度はその2つの数値に依存する別の数値が得られる。
...
* つまり、50%の組み合わせで1が出力されます。つまり、2つの入力ビットがそれぞれ0か1になる確率がほぼ半々であれば、出力ビットも同じように半々になる。
ハッシュ関数を組み合わせる際に、なぜORやANDではなくXORをデフォルトの操作とすべきなのか、その直感や数学的背景を説明してもらえますか?
どのように解決するのですか?
一様乱数(1ビット)の入力を仮定すると、AND関数の出力確率分布は75%になります。
0
と25%です。
1
. 逆に、OR は 25% です。
0
と75%です。
1
.
XOR関数は50%です
0
と50
1
したがって、一様な確率分布を組み合わせるのに適しています。
これは真理値表を書き出すとわかる。
a | b | a AND b
---+---+--------
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
a | b | a OR b
---+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
a | b | a XOR b
---+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
演習:2つの1ビット入力の論理関数はいくつあるか
a
と
b
は、このように一様な出力分布を持つのでしょうか?なぜXORが質問にある目的に最も適しているのでしょうか?
関連
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン