JavaSE集合实现原理——LinkedHashMap

        这是我关于“JavaSE集合实现原理”系列的第二篇博文，这次解析linkedHashMap的实现原理。记得有一次参加面试时，面试官问我：“你说的输入这么多，那你的输出呢？”；我便机智的回答：“写博客、工作当中”。虽然搪塞了过去，但实际上我的博客输出很少（工作中还是有输出的）。什么东西都得自己看了，摸了，分析了，心理才有底有勇气去和别人侃侃而谈（譬如面试）。现在我要立下Flag，坚持写博客，利用好三年黄金期！

        【01】JavaSE集合实现原理——HashMap

图（1） linkedHashMap相关类关系图 

这张自动生成的关系图可能不太友好，在这儿语言描述一下：linkedHashMap继承自HashMap，其中扩展了linkedHashMap.Entry类继承自HashMap.Node类。

类解释（关键的类）：

• linkedHashMap继承自HashMap，进行了扩展：使键值映射Entry有序，默认顺序为插入顺序
• Entry是linkedHashMap的内部类，继承自HashMap.Node，增加了双向链表的功能。这个双向链表作用是保证键值映射（Entry）的增加、遍历是有序的。
• 其他类可以不关注，关于HashMap的类解释请参考【01】

        linkedHashMap是HashMap的增强版，继承自HashMap。增强功能为：记录键值顺序，默认顺序为插入顺序。linkedHashMap中源码相比HashMap就很少了，因为它仅仅需要覆关键的方法即可——操作节点方法（newNode、replacementNode、newTreeNode、replacementTreeNode），在这些方法中将节点在链表（head、tail）中进行相应的操作。

    
    transient linkedHashMap.Entry head;

    
    transient linkedHashMap.Entry tail;

    
    final boolean accessOrder;

head、tail：见名知意：一个用来保存链条的头部元素，一个用来保存链条的尾部元素。元素节点顺序将使用这条链表来做记录。

accessOrder：从注释上面可以清楚的知道，该值用来控制链表顺序是节点插入顺序、还是访问顺序。另外也是控制是LRU，或是FIFO内存淘汰机制的关键参数。

  // ------- 访问控制 ------
   public V get(Object key) {
        Node e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

    public V getOrDefault(Object key, V defaultValue) {
       Node e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }  

  // ------- 插入控制 ------
  Node newNode(int hash, K key, V value, Node e) {
        linkedHashMap.Entry p =
            new linkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    Node replacementNode(Node p, Node next) {
        linkedHashMap.Entry q = (linkedHashMap.Entry)p;
        linkedHashMap.Entry t =
            new linkedHashMap.Entry(q.hash, q.key, q.value, next);
        transferlinks(q, t);
        return t;
    }

    TreeNode newTreeNode(int hash, K key, V value, Node next) {
        TreeNode p = new TreeNode(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    TreeNode replacementTreeNode(Node p, Node next) {
        linkedHashMap.Entry q = (linkedHashMap.Entry)p;
        TreeNode t = new TreeNode(q.hash, q.key, q.value, next);
        transferlinks(q, t);
        return t;
    }

1、节点访问方法get()、getOrDefault()会根据accessOrder的设置来确定是否调整节点位置。

2、*TreeNode()、*Node()将新增节点放置链表末尾。

        linkedHashMap提供了实现该算法的关键方法linkedHashMap#removeEldestEntry ，该方法将在插入新节点时调用：

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

这个方法相信大家都有印象，它是HashMap提供的勾子方法。linkedHashMap的逻辑覆盖很简单，被调用方法removeEldestEntry饭回true时将删除链表头部元素。因此需要了解LRU、FIFO的基本含义：

• LRU：最近最少使用
• FIFO：先进先出          

 从源代码中得知，删除的永远是head这个变量对应的值，再看看节点访问与插入时都是控制节点放置tail变量中就能理解了。