6

HashMapメソッドを使用して、キーインスタンスが「key」と言い、Valueインスタンスが「value」と言う場合、クラスは内部put()で何をしますか。HashMap私たちが言うとき、それはどのように値を取り戻すのhashMap.get(key)ですか？

編集：ここでは詳細は必要ありません。基本的には、全体像と、操作における方法と方法を理解しようとしてequals()いhashcode()ます。put()get()

4

3 に答える 3

18

上の写真について言えば、以下のようになりますkey。Map

アイテムを入れている間。

  1. hashcodeキーの計算
  2. basketそれhashcodeが存在する場合は、キーのequalsメソッドを使用して、そのバスケットのキーを検索し、要素を追加するか置き換えるかを決定します。
  3. そこにない場合は、新しいバスケットを作成し（再ハッシュ）、その要素をそれに追加します。

得る：

  1. hashcodeキーの取得
  2. そのバスケットに行く
  3. キーを繰り返し使用equalsすると、そのバスケットからその要素が返されます。
于 2012-07-19T11:49:47.417 に答える
1

これはIBMjdk1.6で行われていることです（すべてのベンダーでほぼ同じだと思います）

編集

に関してequals、あなたはこの投稿hashcodeを見たいと思うかもしれません。

編集の終わり

 /**
 * Maps the specified key to the specified value.
 * 
 * @param key
 *            the key
 * @param value
 *            the value
 * @return the value of any previous mapping with the specified key or null
 *         if there was no mapping
 */
@Override
public V put(K key, V value) {
    return putImpl(key, value);
}

V putImpl(K key, V value) {
    Entry<K,V> entry;
    if(key == null) {
        entry = findNullKeyEntry();
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
            }
            entry = createHashedEntry(null, 0, 0);
        }
    } else {
        int hash = key.hashCode();
        int index = hash & (elementData.length - 1);
        entry = findNonNullKeyEntry(key, index, hash);
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
                index = hash & (elementData.length - 1);
            }
            entry = createHashedEntry(key, index, hash);
        }
        if ((cache != null) && (hash >> CACHE_BIT_SIZE == 0)
                && (key instanceof Integer)) {
            cache[hash] = value;
        }
    }

    V result = entry.value;
    entry.value = value;
    return result;
}
于 2012-07-19T11:36:04.273 に答える
1

java 8onwordsから、マップエントリを格納するためにリンクリストではなくバランスの取れたツリーを使用することにより、キーで多くの衝突があるオブジェクトのパフォーマンスが向上しますHashMap。主な考え方は、ハッシュバケット内のアイテムの数が特定のしきい値を超えると、そのバケットはエントリのリンクリストの使用からバランスの取れたツリーに切り替わるというものです。ハッシュの衝突が多い場合、これにより最悪の場合のパフォーマンスO(n)がO(log n).

基本的に、バケットが大きくなりすぎると（現在は:) TREEIFY_THRESHOLD = 8、HashMap動的にツリーマップのアドホック実装に置き換えます。このようにして、悲観的になるのではなく、O(n)はるかに良くなりO(log n)ます。

のビン（要素またはノード）は、他のビン（要素またはノード）をTreeNodesトラバースして使用できますが、過密状態の場合はさらに高速なルックアップをサポートします。ただし、通常使用されているビンの大部分は人口過多ではないため、テーブルメソッドの過程でツリービンの存在のチェックが遅れる可能性があります。

Treeビン（つまり、要素がすべてであるビンTreeNodes）は、主にhashCodeによって順序付けられますが、同点の場合、2つの要素が同じ「<code> classCimplements Comparable <C>」である場合、それらのcompareTo()メソッドは次のように使用されます。注文。

通常のノードの約2倍のサイズであるためTreeNodes、ビンに十分なノードが含まれている場合にのみ使用します。また、（削除またはサイズ変更のために）小さくなりすぎると、プレーンビンに戻されます（現在は:) UNTREEIFY_THRESHOLD = 6。十分に分散されたユーザーでの使用hashCodesでは、ツリービンが使用されることはめったにありません。

Javadocへのリンク

コレクションフレームワークの機能強化

于 2017-04-02T14:28:36.227 に答える