32

私はhashCode()Javaのメソッドを調査しており、Stringクラスのメソッドが奇妙であることがわかりました。ソースコードは次のとおりです。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

コード自体は非常に簡単です。しかし、このようにハッシュコードを計算する理由は何だろうか?
なぜ31を選ぶのですか？
value.length - 1 ではなく 0 から始めるのはなぜですか?
これにより、ハッシュコードが互いに衝突しにくくなるという保証はありますか?

4

1 に答える 1

7

はい、たとえば文字列の場合、文字列値に依存するため、ハッシュコードの衝突の可能性は非常に低くなります。new 演算子で文字列を作成しない場合、新しい文字列が既に存在する値と同じである場合、新しい文字列オブジェクトは作成されず、ヒープからの古い値を参照します。この場合、hashCode の値のみが参照されます。予想通りであること。

hashCode の一般的な契約は次のとおりです。

Java アプリケーションの実行中に同じオブジェクトに対して複数回呼び出された場合は常に、オブジェクトの equals 比較で使用される情報が変更されていない限り、hashCode メソッドは一貫して同じ整数を返す必要があります。この整数は、あるアプリケーションの実行から同じアプリケーションの別の実行まで一貫性を保つ必要はありません。

Java 1.2 から、java.lang.String クラスは、文字列のテキスト全体に対して積和アルゴリズムを使用して hashCode() を実装します。[2] たとえば、java.lang.String クラスのインスタンス s が与えられた場合、ハッシュ コード h(s) は次のように定義されます。

h(s)=s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

ここで、用語は Java 32 ビット int 加算を使用して合計されます。s[i] は文字列の i 番目の文字を表し、n は s の長さです。

Apache Harmony での参照用に、hashCode メソッドは次のとおりです。

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}
于 2013-03-20T08:31:59.257 に答える