除算法を使用したハッシュは、h（k）= kmodmを意味します。私はそれを読んだ
mは2の累乗であってはなりません。これは、m = 2 ^ pの場合、hがkのp個の最下位ビットになるためです。通常、2の累乗に近すぎない素数としてmを選択します。
誰かが小さな例で最下位ビット部分を説明できますか？（mod m）が行うのは、結果を範囲mにラップすることだけだと思いました。mが2の累乗である場合、どういうわけか問題を確認できません。
質問する
3941 次
2 に答える
6
コンピュータ内のすべてのデータは、バイナリ データとして保存されます。2 進数は base-2 で表記されます。
データをハッシュする場合は、簡単に比較できるフィンガープリントを作成する必要があります。元のデータとまったく同じではない類似のデータがある場合、同じフィンガープリント (ハッシュ) を作成するべきではありません。
m where を使用するとどうなるかを推測してくださいm = 2^p (p is int >= 0)。たとえば、2^7 は 2^4 の倍数であるため、2^4 から残ったすべてのビットは 0 になります。データの一部を切り捨てます。これは、データが 2 進数の左端のビットで異なる場合、同じハッシュが作成されることを意味します。
例：
k: 1111111111010101
m: 0000000001000000 (2^6)
k(m): 0000000000010101
これについても同じことを行います：
k: 0000000000010101
m: 0000000001000000 (2^6)
k(m): 0000000000010101
ねえ、それは同じハッシュです! これがまさに、2^p から離れた数が選ばれる理由です。このように、ハッシュの計算では左端のビットが重要であり、2 つの類似したデータが同一のハッシュを作成する可能性ははるかに低くなります。
于 2014-02-15T12:23:30.727 に答える