0

http://java-bytes.blogspot.com/2009/10/hashcode-of-string-in-java.htmlによると、「まず、完全なハッシュ アルゴリズムがないという既知の事実があります。衝突はありません。」

著者は理論的にではなく実際に話していますよね?理論的には、ここに完全なハッシュ関数があるため、「特定のオブジェクトに新しい番号を割り当てる」。数は無数にあるため、一意のオブジェクトに割り当てるものは常に存在します。ただし、メモリの量が限られているため、実際にはこれは実現可能ではありません。

4

1 に答える 1

11

通常、ハッシュ関数は、オブジェクトの 1 つのセット (ユニバース) からより小さなオブジェクトのセット (コドメイン) にマップします。一般に、宇宙はすべての文字列の集合またはすべての数字の集合などの無限集合であり、コドメインはすべての 512 ビット文字列の集合または 0 と 0 の間のすべての数字の集合などの有限集合です。 Java では、オブジェクトの関数には、すべて 32 ビット整数である でhashCode表すことができる値のコドメインがあります。int

作者が「完全なハッシュ関数は存在しない」と言っているのは、すべての文字列の無限集合をすべての 32 ビット整数の集合に、少なくとも 1 回の衝突なしにマップする方法はないということだと思います。 . 実際、2 32 + 1 の異なる文字列を選択すると、少なくとも 1 つの衝突が発生することが保証されます。

あなたの主張 - 各オブジェクトに異なるハッシュ コードを割り当てることはできませんか? - ハッシュ関数のコドメインが無限であるという暗黙の仮定を行います。たとえば、文字列のハッシュ関数を構築するためにこのアプローチを試みる場合、文字列は無限に存在するため、ハッシュ関数のコドメインは、可能なすべての自然数のセットと少なくとも同じ大きさである必要があります。ほとんどのプログラミング言語は、このように機能するハッシュ コードをサポートしていませんが、理論的にはこれが機能することは間違いありません。もちろん、通常、ハッシュ関数には有限のコドメインがあるため、これは有効なハッシュ関数としてカウントされないと反対する人がいるかもしれません。

お役に立てれば!

于 2013-04-12T19:15:01.593 に答える