2

のソースコードをArrays.hashCode(char[] c)
確認して、適用されるアルゴリズムがすべての場合にうまく機能することをあまり確認していません。

    public static int hashCode(int a[]) {
    if (a == null)
        return 0;

    int result = 1;
    for (int element : a)
        result = 31 * result + element;

    return result;
}

ここで実装されているハッシュ関数は、すべての入力配列を本当に均一に分散しますか?そして、ここで素数 31 を使用する理由.

4

3 に答える 3

6

なぜ素数 31 を使うのですか?

これは2つに分けられますか？

  1. なんで素数？

ここで、目標はオブジェクトの一意のHashCode を取得することであり、そのオブジェクトを O(1) 時間で見つけるのに役立つことを理解する必要があります。

ここでのキーワードは、一意です。

素数

素数は一意の数です。それらは、素数がそれを構成するために使用されるという事実のために、素数と他の数との積が一意である可能性が最も高いという点で一意です (もちろん、素数自体ほど一意ではありません)。このプロパティは、ハッシュ関数で使用されます。

.

なぜ31番？

効果的な Javaから

  • それは奇妙な素数であり、素数を使用するのは「伝統的」だからです。

  • また、2 のべき乗よりも 1 小さいため、ビットごとの最適化が可能です。

    ここに完全な引用があります、

項目 9 から: equals をオーバーライドするときは常に hashCode をオーバーライドします。

値 31 が選択されたのは、奇素数だからです。偶数で乗算がオーバーフローした場合、2 による乗算はシフトと同等であるため、情報が失われます。素数を使用する利点はあまり明確ではありませんが、伝統的なものです。

31 の優れた特性は、パフォーマンスを向上させるために、乗算をシフト (§15.19) と減算に置き換えることができることです。

31 * i == (i << 5) - i 最新の VM は、この種の最適化を自動的に行います。

この項目のレシピはかなり優れたハッシュ関数を生成しますが、最先端のハッシュ関数を生成するわけではなく、リリース 1.6 の Java プラットフォーム ライブラリもそのようなハッシュ関数を提供しません。このようなハッシュ関数を記述することは研究テーマであり、数学者や理論計算機科学者に任せるのが最善です。

おそらく、プラットフォームの今後のリリースでは、平均的なプログラマーがそのようなハッシュ関数を構築できるように、そのクラスとユーティリティ メソッドに最先端のハッシュ関数が提供されるでしょう。それまでの間、この項目で説明されている手法は、ほとんどのアプリケーションに適しています。

これは非常に良いソースです。

于 2013-09-13T14:04:26.610 に答える
1

この投稿を参照してください: Java の hashCode() in String は乗数として 31 を使用するのはなぜですか?

それがTheEwookの答えです。

一般に素数を使用するのは、因数がなく、N を法としてより適切に分散するためです。ここで、N はビニングする範囲のサイズです。31 は小さくて奇数の素数なので、うまく機能します。ただし、インターネットで見つけられるさまざまなソースが示すように、31 のような小さな素数は、大きな素数よりも多くの衝突を引き起こす可能性があります (特に、ハッシュされる値が最初から十分に分散されていない場合)。パフォーマンスが思ったほど良くない場合は、素数を大きくしてください。

于 2013-09-13T14:13:48.137 に答える
1

奇素数であるため、値 31 が選択されました。偶数で乗算がオーバーフローした場合、2 による乗算はシフトと同等であるため、情報が失われます。素数を使用する利点はあまり明確ではありませんが、伝統的なものです。31 の優れた特性は、パフォーマンスを向上させるために乗算をシフトと減算に置き換えることができることです: 31 * i == (i << 5) - i. 最新の VM は、この種の最適化を自動的に行います。

于 2013-09-13T14:03:07.647 に答える