2

の実装ですHashMap。

ビンのインデックスを取得するための次のコードを提供します。

private int getIndex(K key)
{
    int hash = key.hashCode() % nodes.length;
    if (hash < 0)
        hash += nodes.length;
    return hash;
}

ハッシュ値がテーブルのサイズよりも大きくならないようにするために、ユーザー提供のハッシュ関数の結果がテーブルの長さを法として使用されます。インデックスは負でない必要がありますが、左側のオペランド (ハッシュ値) が負の場合、モジュラス演算子 (%) は負の数を返すため、それをテストして非負にする必要があります。

hash非常に大きな負の値であることが判明した場合hash += nodes.length、サイクル内の追加には多くの処理が必要になる場合があります。

O(1)そのためのアルゴリズムが必要だと思います（hash値に関係なく）。

もしそうなら、どのようにそれを達成することができますか？

4

2 に答える 2

3

非常に大きな負の数になることはできません。

の結果anything % nodes.lengthは常に絶対値よりも小さいため、ループではなくnodes.length単一の が必要です。ifこれはまさにコードが行うことです：

if (hash < 0) /* `if', not `while' */
    hash += nodes.length;
于 2012-11-28T09:33:36.723 に答える
1

これは、 HashMapが実際に使用するアプローチではありません。

272       /**
273        * Returns index for hash code h.
274        */
275       static int indexFor(int h, int length) {
276           return h & (length-1);
277       }

lengthは常に 2 のべき乗であり、これは符号なしと同じであるため、これは機能します。 % length

hash が非常に大きな負の値であることが判明した場合、サイクル内の hash += nodes.length の追加に多くの処理が必要になる場合があります。

この時点でのハッシュは and の間-length+1にある必要がlength-1あるため、非常に大きな負の値にすることはできず、負の値にするとコードは機能しません。いずれにせよ、値がどれだけ大きくても、コストは常に同じです。

于 2012-11-28T09:49:09.003 に答える