-3

hは任意のハッシュ関数であり、キーをサイズ のテーブルにハッシュするために使用されますn。mここn<=mで、特定のキーに関連する衝突の予想数xは次のとおりです。

(A) Less than 1
(B) Less than n
(C) Less than m
(D) Less than n/2

私が理解したのは、それよりも少ないはずnですが、よくわかりません。

4

1 に答える 1

2

あなたは誕生日のパラドックスをよく読んでください。

ここにいくつかのリンクがあります：

誕生日の問題

誕生日のパラドックスを理解する

そして2番目のリンクからの引用：

誕生日のパラドックスからのいくつかの教訓は次のとおりです。

  • sqrt（n）は、n個のアイテムと50％の確率で一致するために必要な数値です。sqrt（365）は約20です。これは、誕生日攻撃の暗号化で機能します。
  • 2 ^ 128（1e38）のGUIDがありますが、衝突の可能性が50％になる前に、2 ^ 64（1e19）しか使い切ることができません。そして、50％は本当に本当に高いです。
  • 一致する可能性が95％になるには、13人がアルファベットの文字を選択するだけで済みます。上で試してください（人= 13、アイテム= 26）。
  • 指数関数的成長は、ユニークなアイテムを選ぶ可能性を急速に減らします（別名、試合のチャンスを増やします）。覚えておいてください：指数は直感的ではなく、人間は利己的です！
于 2013-01-19T14:35:14.783 に答える