集合框架 -- LinkedHashMap

LinkedHashMap

继承自HashMap，加上了链表的结构来实现顺序迭代，有两种迭代顺序，一种是按照数据插入的顺序，一种是按照数据访问的顺序

基础源码

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;
    final boolean accessOrder;  //true 访问顺序遍历，false 插入顺序遍历（默认）

继承了HashMap，Entry类中添加了before和after对象

构造函数

public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

调用了HashMap的构造函数，给accessOrder赋值

put方法

public V put(K key, V value) {                                           
    return putVal(hash(key), key, value, false, true);                   
}       

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

直接调用了HashMap的put方法，但是HashMap的put方法中留出了afterNodeAccess和afterNodeInsertion方法

newNode方法

重写了newNode方法，维护了一个双向链表，可以用来记录数据插入的顺序

afterNodeInsertion方法

这个方法里面只是做一个判断，默认removeEldestEntry返回false，如果是通过改变accessOrder来实现LRUcatch的时候将返回值改为true，可以实现数据超过缓存阈值时对最老的数据进行删除

afterNodeAccess方法

accessOrder被设置为true，也就是按照访问顺序进行迭代的时候，会将被修改的元素放到链表的尾部

get方法

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

获取数据调用父类方法，只是之后根据accessOrder判断是否需要去对链表结构进行修改，同时由于afterNodeAccess中修改了modCount值，所以在迭代的时候进行get操作也会报异常

LinkedHashIterator

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

重写了迭代器，迭代的是内部维护的双向链表