Java-LinkedHashMap

Java-LinkedHashMap 一、介绍

linkedHashMap 继承 了 HashMap。linkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。具有一定的顺序性。

HashMap可以参考之前的文章：https://so.csdn.net/so/search?q=HashMap&t=blog&u=weixin_43732955

public class linkedHashMap extends HashMap implements Map

存储结构：

二、源码分析

那么linkedHashMap底层是如何维护插入顺序的双链表的呢。
​

2.0 初始化

  public linkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

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

可以看到 linkedHashMap底层是调用 HashMap的构造方法信息初始化

2.1 插入

插入方法为map.put()方法但是我们看到 linkedHashMap类中并没有实现，其方法是继承了HashMap中的put方法。

/
   *  hash(key) 方法在jdk1.8中进行是 高位异或 目的就是为了增加散列程度
     *  
     */

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


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // 数组为空 那么初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        // 不存在
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 存在
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

            // 已转换为红黑树，进行红黑数的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {

                for (int binCount = 0; ; ++binCount) {
                    //尾插入法 插入到最后一个元素的后面
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8 也就是存储链表的第9个元素之后
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                            // 红黑数转换
                            treeifyBin(tab, hash);
                        break;
                    }
                    //遍历过程判断是否存在相同的key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果有存在key 与put进入的key相同
            //进行元素覆盖  相同的key的 覆盖
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                
                //
                // 方法回调： key被访问后
                afterNodeAccess(e);
                
                return oldValue;
            }
        }


        
        ++modCount;
        if (++size > threshold)
            resize();

        //
        // 方法回调：key被插入后 
        afterNodeInsertion(evict);
        return null;
    }

在put方法中有两个重要的回掉用函数：afterNodeAccess() 和 afterNodeInsertion(),下面来分别介绍一下这两个函数的作用；

afterNodeAccess 表示在节点值被访问之后的 *** 作，在linkedHashMap被重写，将访问的节点移在链表的尾部 。

void afterNodeAccess(Node e) { // move node to last
    // 用 last 表示插入 e 前的尾节点
    // 插入 e 后 e 是尾节点, 所以也是表示 e 的前一个节点
    linkedHashMap.Entry last;
    //如果是访问序，且当前节点并不是尾节点
    //将该节点置为双向链表的尾部
    if (accessOrder && (last = tail) != e) {
        // p: 当前节点
        // b: 前一个节点
        // a: 后一个节点
        // 结构为: b <=> p <=> a
        linkedHashMap.Entry p =
            (linkedHashMap.Entry)e, b = p.before, a = p.after;
        // 结构变成: b <=> p <- a
        p.after = null;

        // 如果当前节点 p 本身是头节点, 那么头结点要改成 a
        if (b == null)
            head = a;
        // 如果 p 不是头尾节点, 把前后节点连接, 变成: b -> a
        else
            b.after = a;

        // a 非空, 和 b 连接, 变成: b <- a
        if (a != null)
            a.before = b;
        // 如果 a 为空, 说明 p 是尾节点, b 就是它的前一个节点, 符合 last 的定义
      	// 这个 else 没有意义，因为最开头if已经确保了p不是尾结点了，自然after不会是null
        else
            last = b;

        // 如果这是空链表, p 改成头结点
        if (last == null)
            head = p;
        // 否则把 p 插入到链表尾部
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion()方法

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

2.2 删除

也是用HashMap.remove(e)方法，在内部同样也有一个回调函数：
afterNodeRemoval(node)  在 linkedHashMap的重写如下：
	
    
    void afterNodeRemoval(Node e) { // unlink
        linkedHashMap.Entry p =
            (linkedHashMap.Entry)e, b = p.before, a = p.after;
        // b - > p -> a
        p.before = p.after = null;
        // p 是头节点 那么 p.next 变为头节点
        if (b == null)
            head = a;
        else
            b.after = a;
        // p是不是尾节点 如果是那么尾 节点为b 
        if (a == null)
            tail = b;
        // 连接前节点
        else
            a.before = b;
    }

三、linkedHashMap 实现 LRU

基于上述的回调函数，我们可以很快就构建一个 LRU的一个缓存存储结构。

class LRUCache extends linkedHashMap{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    // 
    public void put(int key, int value) {
        super.put(key, value);
    }
	
    
    /**
    * removeEldestEntry 在插入时 ，当evict为ture时，回调该函数
    * 用来判断 删除队头的 条件
    /
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity; 
    }
}

参考：

搞懂 Java linkedHashMap 源码