LinkedHashMap如何实现迭代时有序

LinkedHashMap具有可预知的迭代顺序，根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。  

默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。  可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。

如何实现迭代有序？

1. 重新定义了数组中保存的元素Entry（继承于HashMap.Entry)，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。仍然保留next属性，所以既可像HashMap一样快速查找，用next获取该链表下一个Entry，也可以通过双向链接，通过after完成所有数据的有序迭代。
2. accessOrder为true时，按访问顺序排序，false时，按插入顺序排序。默认false，即下文中recordAccess方法没有改变什么。

   <span style="font-size:14px;">private final boolean accessOrder;</span>
              

3. 存储put LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
   • put时，key已存在，替换value（同HashMap），并调用recordAccess方法，方法作用为根据accessOrder的值保持链表顺序不变或者将将访问的当前节点移到链表尾部(头结点的前一个节点)。
   • key不存在，添加新的Entry，仍然是Table[i]= newEntry，旧链表首个为newEntry.next（同HashMap）,将newEntry加到双向链表末尾（即header前，这样就保留了插入顺序）。

HashMap.put:

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }  
           

重写方法：

void recordAccess(HashMap<K,V> m) {  
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
            if (lm.accessOrder) {  
                lm.modCount++;  
                remove();  
                addBefore(lm.header);  
            }  
        }  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 调用create方法，将新元素以双向链表的的形式加入到映射中。  
    createEntry(hash, key, value, bucketIndex);  
  
    // 删除最近最少使用元素的策略定义  
    Entry<K,V> eldest = header.after;  
    if (removeEldestEntry(eldest)) {  
        removeEntryForKey(eldest.key);  
    } else {  
        if (size >= threshold)  
            resize(2 * table.length);  
    }  
}  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K,V> old = table[bucketIndex];  
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
    table[bucketIndex] = e;  
    // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。  
    e.addBefore(header);  
    size++;  
}  
private void addBefore(Entry<K,V> existingEntry) {  
    after  = existingEntry;  
    before = existingEntry.before;  
    before.after = this;  
    after.before = this;  
}  
           

4.读取

同样调用recordAccess方法，是否将访问的当前节点移到链表尾部，与HashMap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前节点移到链表尾部(头结点的前一个节点)。

public V get(Object key) {  
    // 调用父类HashMap的getEntry()方法，取得要查找的元素。  
    Entry<K,V> e = (Entry<K,V>)getEntry(key);  
    if (e == null)  
        return null;  
    // 记录访问顺序。  
    e.recordAccess(this);  
    return e.value;  
}  
           

5. 迭代

//返回链表下个节点的引用
        Entry<K,V> nextEntry() {
            //快速失败机制
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //链表为空情况
            if (nextEntry == header)
                throw new NoSuchElementException();
            
            //给lastReturned赋值，最近一个从迭代器返回的节点对象
            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }