LinkedHashMap

public class LinkedHashMap<K,V>
        extends java.util.HashMap<K,V>
        implements Map<K,V>
{
    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;//定义一个前驱，一个后继节点
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    transient LinkedHashMapEntry<K,V> head;//Linked的头
    transient LinkedHashMapEntry<K,V> tail;//linked的尾

    /**
     * 这个linkedHashMap以什么规则排序：
     * true:以访问顺序排序，那么当链表中的元素有被访问到，就会转移到链表表尾，最近最少访问（LRU）的的node放在队头。
     *      通常LRUCache中都维护着一个LinkedHashMap，参数为true。
     * false:按插入顺序排序，默认就是这种。
     */
    final boolean accessOrder;


    // 把节点p连接到kinked的队尾
    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;//标记尾节点
        tail = p;//p成为新的尾节点
        if (last == null)
            //如果这轮添加节点的操作之前就没有tail,说明head也是null,
            // 即这是第一次添加操作，那就让p也成为头节点
            head = p;
        else {
            //p节点和之前的tail连接，双向引用
            p.before = last;
            last.after = p;
        }
    }

    // 用目标节点dst替换原节点src
    private void transferLinks(LinkedHashMapEntry<K,V> src,
                               LinkedHashMapEntry<K,V> dst) {
        LinkedHashMapEntry<K,V> b = dst.before = src.before;
        LinkedHashMapEntry<K,V> a = dst.after = src.after;
        if (b == null)
            head = dst;
        else
            b.after = dst;
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        //创建一个新的节点
        LinkedHashMapEntry<K,V> p = new LinkedHashMapEntry<K,V>(hash, key, value, e);
        //添加新的节点
        linkNodeLast(p);
        //返回新创建的节点
        return p;
    }

    //替换节点
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
        LinkedHashMapEntry<K,V> t = new LinkedHashMapEntry<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    //创建树节点
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    //替换树节点
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    //node被删除之后，从链表中删除
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    //节点被put进Hashmap之后调用，参数evict表示是否要在插入元素之后考虑删除最老的元素，hashmap的实现默认是true
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            //如果removeEldestEntry（first）返回true，就把first节点remove
            //这个方法默认是返回false，所以需要子类根据自己的需求重写该方法（根据链表长度最大值和当前size判断）
            
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    //节点在被访问之后的操作，如果accessOrder，就将访问的节点转移到队尾
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<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 internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }


    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

 
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }


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


    /**
     * 是否存在一个node,它的value和参数的value是相同的，包括满足equals
     */
    public boolean containsValue(Object value) {
        for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }

    /**
     * 根据Key获取value
     */
    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            //如果是访问顺序排序的，就需要在本次访问之后，将这个node转移到队尾。
            afterNodeAccess(e);
        return e.value;
    }

    /**
     * get如果没找到就返回个默认的 defaultValue。
     */
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return defaultValue;
        if (accessOrder)
            //如果是访问顺序排序的，就需要在本次访问之后，将这个node转移到队尾。
            afterNodeAccess(e);
        return e.value;
    }

    /**
     * 清空
     */
    public void clear() {
        super.clear();
        head = tail = null;
    }

    // Android-added: eldest(), for internal use in LRU caches
    /**
     * 返回最老的节点，head就是最老的，如果是empty，返回null
     */
    public Map.Entry<K, V> eldest() {
        return head;
    }

    //判断是否要删除最老的节点
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}