4

Java HashTable クラスの hashCode() 実装を次に示します。ハッシュテーブルの要素数が膨大で、ハッシュコードが INTEGER MAX LIMIT -2,147,483,648 から 2,147,483,647 を超える場合はどうなりますか? hashCodes は正の整数になると思います。

 public synchronized int hashCode() {

    int h = 0;
    if (count == 0 || loadFactor < 0)
        return h;  // Returns zero

    loadFactor = -loadFactor;  // Mark hashCode computation in progress
    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        for (Entry e = tab[i]; e != null; e = e.next)
            h += e.key.hashCode() ^ e.value.hashCode();
    loadFactor = -loadFactor;  // Mark hashCode computation complete

    return h;
}
4

2 に答える 2

13

hashCodes は正の整数になると思います。

いいえ、必ずしもそうではありません。それらは単なる整数です。それらは間違いなく負になる可能性があり、ハッシュコードの計算中に整数オーバーフローが発生しても問題ありません。理想的なハッシュ コードは、その範囲全体に均一に分散されます (intこの場合)。ハッシュコードを使用するものはすべて、値が負になる可能性を考慮する必要があります。

于 2012-06-20T06:23:11.440 に答える
0

整数でオーバーフローが発生することは、ニーズに適さない場合があります。私は時々これを言います。私はまだこの状況に遭遇していませんが、それを防ぎたいと思います。

ハッシュコードの生成に使用するコードを貼り付けます。私は通常、オブジェクトからすべての変数を取得し、それらを文字列に変換して計算を行うことでそれを行います。

public static int generateHashCode(String ... args)
{
    int length = 0;
    char[] cArray = null;
    if(args.length == 1) {
        length = args[0].length();
        cArray = args[0].toCharArray();
    }
    else {
        for(int i = 0; i < args.length; i++) {
            length += args[i].length();
        }

        cArray = new char[length];
        int incrementer = 0;
        for(int i = 0; i < args.length; i++) {
            String str = args[i];
            for(int j = 0; j < str.length(); j++) {
                cArray[incrementer] = str.charAt(j);
                ++incrementer;
            }
        }
    }

    int h = 0;
    for (int i = 0; i < cArray.length; i++) {
        h = 31*h + cArray[i];
    }

    return h;
}
于 2012-06-20T06:31:49.150 に答える