JavaコレクションフレームワークLinkedHashSetとLinkedHashMapのソースコード解析の詳細説明（画像）

全体の紹介

HashSet と HashMap、そして TreeSet と TreeMap についてこれまでの説明を読んだことがあれば、LinkedHashSet と LinkedHashMap はなるこの記事で説明しているものは実際には同じものです。 LinkedHashSet と LinkedHashMap も Java で同じ実装を持っています。前者は後者をラップするだけです。つまり、LinkedHashSet には LinkedHashMap (アダプター モード) があります。したがって、この記事ではLinkedHashMapの分析に焦点を当てます。

LinkedHashMapはMapインターフェースを実装しています。これにより、keyがnullである要素を挿入できるようになり、valueの挿入も可能になりますcode> を null 要素にします。名前からわかるように、このコンテナは、リンクされたリストkey为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。

事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部（是一个哑元），该双向链表的迭代顺序就是entry的插入顺序。

除了可以保迭代历顺序，这种结构还有一个好处：迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心：hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要*@Override*hashCode()和equals()方法。

通过如下方式可以得到一个跟源Map迭代顺序一样的LinkedHashMap：

void foo(Map m) {
    Map copy = new LinkedHashMap(m);

}

出于性能原因，LinkedHashMap是非同步的（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将LinkedHashMap包装成（wrapped）同步的：

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

方法剖析

get()

get(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样，读者可自行参考前文，这里不再赘述。

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

注意，这里的插入有两重含义：

1. 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entryと

   HashMap🎜本体、つまり、🎜HashMap🎜と🎜リンクリスト🎜の両方の特定の特性を満たします。 🎜LinkedHashMap🎜は、🎜リンクリスト🎜で強化された🎜HashMap🎜と考えてください。 🎜🎜🎜🎜🎜実際、🎜LinkedHashMap🎜は🎜HashMap🎜の直接のサブクラスです。この2つの唯一の違いは、🎜LinkedHashMap🎜は🎜HashMap🎜に基づいており、二重リンクリストを使用してすべてのを結合することです。要素の反復順序が挿入順序🎜と同じになるように、entry が接続されています。上図は🎜LinkedHashMap🎜の構造図を示しています。主要部分は🎜HashMap🎜と全く同じですが、二重リンクリストの先頭を指すheaderが追加されています(ダミー要素)。 , 🎜二重リンクリストの繰り返し 順序はentry🎜の挿入順です。 🎜🎜反復順序を維持することに加えて、この構造には別の利点もあります。🎜反復🎜LinkedHashMap🎜は、🎜HashMap🎜のようにtable全体を走査する必要はなく、header が指す二重リンクリストで十分です🎜。つまり、🎜LinkedHashMap🎜 の反復時間は entry の数にのみ関係し、 table のサイズ。 🎜🎜LinkedHashMap🎜のパフォーマンスに影響を与える可能性のあるパラメーターは 2 つあります: 初期容量と負荷率です。初期容量は初期の table サイズを指定し、負荷係数は自動拡張の重要な値を指定するために使用されます。 entry の数が capacity*load_factor を超えると、コンテナは自動的に拡張され、再ハッシュされます。多数の要素が挿入されるシナリオの場合、より大きな初期容量を設定すると、再ハッシュの数を減らすことができます。 🎜🎜オブジェクトを🎜LinkedHashMap🎜または🎜LinkedHashSet🎜に入れる場合、2つの方法がありますhashCode() と equals() には特別な注意が必要です。 🎜hashCode() メソッドは、オブジェクトがどの bucket に配置されるかを決定します。複数のオブジェクトのハッシュ値が競合する場合、equals()メソッドは、これらのオブジェクトが「同じオブジェクト」であるかどうかを判断します🎜。したがって、カスタム オブジェクトを LinkedHashMap または LinkedHashSet に配置する場合は、 *@Override*hashCode() と が等しい必要があります。 () メソッド。 🎜🎜次の方法で、ソース🎜Map🎜🎜反復順序🎜と同じ🎜LinkedHashMap🎜を取得できます: 🎜

   // LinkedHashMap.addEntry()
   void addEntry(int hash, K key, V value, int bucketIndex) {
       if ((size >= threshold) && (null != table[bucketIndex])) {
           resize(2 * table.length);// 自动扩容，并重新哈希
           hash = (null != key) ? hash(key) : 0;
           bucketIndex = hash & (table.length-1);// hash%table.length
       }
       // 1.在冲突链表头部插入新的entry
       HashMap.Entry<K,V> old = table[bucketIndex];
       Entry<K,V> e = new Entry<>(hash, key, value, old);
       table[bucketIndex] = e;
       // 2.在双向链表的尾部插入新的entry
       e.addBefore(header);
       size++;
   }

   🎜パフォーマンス上の理由から、🎜LinkedHashMap🎜は、必要な場合は非同期です(同期されていません)。マルチスレッド環境で使用する場合、プログラマ は手動で同期する必要があります。または、🎜LinkedHashMap🎜 が次のようにラップされて同期されます: 🎜🎜Map m = Collections.synchronizedMap (new LinkedHashMap(. ..));🎜🎜メソッド分析🎜

   get()

   🎜get(<a href="http://www.php.cn/%20wiki/60.html%20" target="_blank">Object</a> key) メソッドは、指定された key 値に基づいて、対応する value を返します。このメソッドのプロセスは HashMap.get() メソッドとほぼ同じです。読者は前の記事を参照してください。ここでは詳しく説明しません。 🎜

   put()

   🎜put(K key, V value) メソッドは、指定された key, value ペアを map の内部。このメソッドは、まず <code>map を検索して、タプルが含まれているかどうかを確認します。含まれている場合、検索プロセスは get() メソッドと似ています。見つからない場合は、addEntry(int hash, K key, V value, intbucketIndex) メソッドを通じて新しい entry が挿入されます。 🎜🎜ここでの 🎜 の挿入には 2 つの意味があることに注意してください🎜: 🎜

   1. 🎜 table の観点から見ると、新しい entry

   は、対応する bucket に挿入する必要があります。ハッシュの競合がある場合は、ヘッド挿入メソッドを使用して新しい entry をヘッドに挿入します。競合リンクされた部門のリスト。 🎜

2. 从header的角度看，新的entry需要插入到双向链表的尾部。

addEntry()代码如下：

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下：

// LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

上述代码只是简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应引用）。查找过程跟get()方法类似。

注意，这里的删除也有两重含义：

1. 从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。

2. 从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。

removeEntryForKey()对应的代码如下：

// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单，这里不再赘述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }

}

以上がJavaコレクションフレームワークLinkedHashSetとLinkedHashMapのソースコード解析の詳細説明（画像）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。