こんにちは、整数のリストを取り、新しいを返すハッシュinteger関数を提案できますか? 評価が速く、多かれ少なかれ衝突に強いはずです。近似検索アルゴリズム (LSH など) で使用する予定です。
hashCode()リストの Javaでは、次の式を使用します。
31 + SUM 31^(i+1) *a[i]
耐衝突性がある理由を誰かが知っていますか? 素数は 31 程度だと思いますが、それを証明する方法がわかりません。
質問する
830 次
1 に答える
1
式が間違っています（逆にカウントされます）。実際には次のとおりです。
SUM 31^(n-1-i) * a[i]
ここでnはリストの長さで、a[-1] = 1 も使用します。または、個別に使用する場合は、
31^n + SUM 31^(n-1-i) * a[i]
(そして、Java の int の場合と同様に、結果はモジュロ 2^32 になります。)
Java のhashCode()for List ( java.util.Listで指定され、このクラスのすべての実装によって実装されることになっている) は、暗号の意味で衝突耐性がありません。つまり、衝突を見つけるのは難しくありません。
複数の要素を持つ整数のリストが与えられた場合、そのうちの 1 つを 1 増やし、次のものを 31 減らす (またはその逆) と、同じハッシュ コードを持つ 2 番目のリストを作成できます。
たとえば、2 つのリスト[1, 0]と[0, 31]のハッシュ コードは同じです992 = 31·32 = (1·31 + 1)·31 + 0 = (1·31 + 0)·31 + 31。
偶発的な衝突に対して弱い耐性があります。これは、実際には 31 が素数である (つまり、実数の約数がない) という事実に関連しており、整数 (または他のオブジェクトのハッシュコード) の「自然に発生する」リストは、ちょうどこの量。
もちろん、リストのリストを作成すると、それぞれがハッシュ コードに同じ戦略を使用するため、簡単に衝突が発生[ [0, 1], [0, 0] ]します。[ [0, 0], [1, 0] ]同じハッシュ コード 31³+2·31²+31 = 31744 も含まれます。
于 2013-05-11T15:45:10.577 に答える