LinkedHashMap

LinkedHashMap定义

LinkedHashMap继承于HashMap，本身就是一个HashMap，只是增加了一个双向链表按顺序保存KEY。

    ......
    private transient Entry<K,V> header;
    private final boolean accessOrder;

    ......

 

属性accessOrder

accessOrder定义了双向链表中节点的排序方式：true表示按照访问顺序排序，即在map上每执行一次get(key),该key所对应的Entry节点在链表中向前移动一个节点，也就是说map中访问越频繁的key越排在链表的前面；表示链表的顺序为key/value对put到map中的顺序，即与插入顺序保存一致。

 

属性Entry

Entry表示为双向链表中的节点，包含一个前向指针和后向指针，其定义如下：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
        Entry<K,V> before, after;

        private void remove() {
            before.after = after;
            after.before = before;
        }

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

其中recordAccess方法就是根据accessOrder 值来决定当前节点在链表中的顺序。

 

 

内部类LinkedHashIterator

LinkedHashIterator是一个静态抽象的内部类，主要提供了对双向链表的迭代，定义如下：

private abstract class LinkedHashIterator<T> implements Iterator<T> {
    Entry<K,V> nextEntry    = header.after;
    Entry<K,V> lastReturned = null;

    int expectedModCount = modCount;

    public boolean hasNext() {
            return nextEntry != header;
    }

    public void remove() {
        if (lastReturned == null)
        throw new IllegalStateException();
        if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
    }

    Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
    }
}

这里我们需要关注的是红色标注的expectedModCount， 该变量通过与HashMap 的 modCount(修改次数，map上发生put、remove、clear时就modCount++)进行比较从而判断在链表迭代的过程中该HashMap有没有发生并发修改，从而抛出并发异常ConcurrentModificationException。

 

内部类KeyIterator

KeyIterator是对LinkedHashIterator的继承实现，这里不再描述。