LinkedHashMap代码详解(一)

HashMap 在遍历map时，数据是无序的，在某些需要按照put顺序遍历时，就用到了LinkedHashMap，LinkedHashMap是HashMap的子类，并且用一条双向链表来存储数据插入的顺序

transient LinkedHashMap.Entry<K,V> head; //链表的头节点
transient LinkedHashMap.Entry<K,V> tail; //链表的尾节点
final boolean accessOrder;               //是否开启lru算法(最活跃的点放在链表头部)

put():
由于LinkedHashMap没有put方法，put操作用的还是HashMap的方法，但是重写了newNode(int hash, K key, V value, Node e) ，afterNodeAccess(Node e),afterNodeInsertion(boolean evict)方法
1 table中不存在相同的key

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

LinkedhashMap重写了newNode方法，将新增的节点加入链表尾部，上代码

   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)//如果原尾节点为空，证明链表还没有数据，头节点指向新节点p
            head = p; 
        else {        //链表不为空
            p.before = last; 
            last.after = p;//原尾节点建立双向链接
        }
    }

2 table数组中存在相同的key

           if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

发生了节点数据操作(value替换)，如果开启了LRU(accessOrder=true)，则将修改的节点放入链表尾部，HashMap.afterNodeAccess() 为空函数
LinkedHashMap overwirte了该方法

      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;
              
            /**重写上面的赋值操作
            LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e；
            LinkedHashMap.Entry<K,V> b(befor) = p.before；
            LinkedHashMap.Entry<K,V> a(after) = p.after;           
            **/
            p.after = null; //将修改的节点after置为null
            if (b == null)  //如果b==null  证明e是头结点
                head = a;  //将链表头结点指向 e.next
            else            //e不是头结点
                b.after = a;  // e.befor.after = e.after
                             // e节点的上一个节点的next指向e的下一个节点,移除e
            if (a != null)   //如果e的下一个节点不为空
                a.before = b;//e.after.befor= e.after
                             // e节点的下一个节点的befor指向e的上一个节点，双向链表的反向箭头
            else             // a == null e是尾部节点
                last = b;    //last指向e的上一个节点
            if (last == null) //如果 last== null 证明 只有一个节点
                head = p;      //头部尾部都指向该节点
            else {              // p不是头节点
                p.before = last; //将p放在链表尾部 
                last.after = p;
            }
            tail = p;
            ++modCount;        //map操作数+1，(重新赋值且开启LRU，modCount会两次+1)
        }
    }

3 在执行完put操作后，调用afterNodeInsertion方法

    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;
    }

evict 在hashMap中默认为true，LinkedHashMap.removeEldestEntry ()默认返回false，
该方法的yongfasj用法是 配合LRU算法，自定义Class继承LinkedHashMap方法并重写removeEldestEntry 方法，
在特定条件下返回true，移除链表中最左侧的节点
可以使用该特性进行缓存创建，保留最近活跃的数据，开启LRU需要将开头提到的accessOrder 置为true

该参数只能在LinkedHashMap new时指定，需要同时指定扩展因子loadFactor 默认为0.75f

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

get():
LinkedHashMap get方法，可以看到 和hashMap是一致的，只是加了accessOrder 判断，开启LRU后，将获取的数据放在链表的最右侧，提高该节点的活跃程度

    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;
    }