6

私はハッシュテーブルのputメソッドのJavaの実装を調べていて、これに出くわしました：

// Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

衝突をチェックするにはキーが必要であることを理解していますが、なぜJavaはキーのハッシュ値を保存し、それもチェックするのですか？

4

2 に答える 2

8

同じバケット（tab）は、操作によってハッシュが異なるアイテムを保持できるため% tab.lengthです。equals()最初にハッシュをチェックすることは、ハッシュが異なる場合に呼び出さないようにするためのパフォーマンスの最適化である可能性があります。

equals()これを例に挙げると、コストのかかるメソッドを持つ2つの複雑なオブジェクトがあるとします。一方のオブジェクトのハッシュは1に等しく、もう一方のオブジェクトのハッシュは32です。両方のオブジェクトを31個のバケットを持つハッシュテーブルに配置すると、それらは同じバケット（tab）になります。2番目の（別のオブジェクト）を追加するときは、それがまだテーブルにないことを確認する必要があります。equals()すぐに使用できますが、遅くなる可能性があります。equals()代わりに、最初にハッシュを比較し、必要がなければコストのかかるものを避けます。この例では、ハッシュは（同じバケット内にあるにもかかわらず）異なるため、equals()必要ありません。

于 2012-10-18T19:26:04.717 に答える
1

アクセスごとにハッシュ値を再計算する必要がないため、アクセスが高速になります。これは、明示的な検索（実行する前にハッシュがチェックされるequals）だけでなく、再ハッシュにとっても重要です。

于 2012-10-18T19:34:21.580 に答える