LRU相关

    在刷leetcode的时候看到的自己设计一个LRU缓存，所以延伸的把LinkedHashMap看了一下。

    LinkedHashMap是HashMap的扩展，主要是利用双向链表实现保存插入顺序或者访问顺序的功能。

    LRU的话就是将accessOrder在初始化的时候传入

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

正常不传入就是false。如果为true的话，会发现在操作（get，put等）的时候都会调用一个方法：

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

就是将访问的这个节点往后放，所以最新访问的都是在最后的！LinkedHashMap里面的get和getOrDefault里面都判断的是否accessOrder为true，其实afterNodeAccess里面也判断了丫?而且HashMap里面putVal和replace之类的都直接调用了afterNodeAccess，但是get里面没有写，有点乱哦。。

如果你只传入了accessOrder，其实他是不会自己给你删除那些过期的节点的，你可以自己遍历实现删除头结点（最近最少使用的），你也可以实现方法removeEldestEntry，默认的是false

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

实现了这个方法以后，就可以在putVal以后，进行删除节点了

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ...
    if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    ...
    afterNodeInsertion(evict);
    return null;
}

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

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
            ...
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<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;
}

从源码就可以看出来了，在新增节点的时候，如果是以前存在的节点，会调用afterNodeAccess把他的顺序调整到最后。新增完成以后，调用afterNodeInsertion判断是不是达到了删除最早节点的要求，达到后就调用removeNode操作进行删除，也就是将hashMap中的节点删除(调整next指针)，这个删除以后还要调用afterNodeRemoval将双向链表里面的删除(调整before和after指针)，到此，就结束一次添加操作。

总结就是，添加的时候，先添加/调整顺序，再删除；获取的时候，调整顺序。

然后我看了几个其他开源项目的LRUCache实现，好像差不多都是利用了LinkedHashMap

com.mysql.jdbc.util

public class LRUCache extends LinkedHashMap<Object, Object> {
    private static final long serialVersionUID = 1L;
    protected int maxElements;

   public LRUCache(int maxSize) {
      super(maxSize, 0.75F, true);
      this.maxElements = maxSize;
   }

   /*
    * (non-Javadoc)
    * 
    * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
    */
   @Override
   protected boolean removeEldestEntry(Entry<Object, Object> eldest) {
      return (size() > this.maxElements);
   }
}

很简单，就是写了一下removeEldestEntry方法。

com.alibaba.dubbo.common.utils

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = -5167631809472116969L;
    private static final float DEFAULT_LOAD_FACTOR = 0.75F;
    private static final int DEFAULT_MAX_CAPACITY = 1000;
    private volatile int maxCapacity;
    private final Lock lock;

    public LRUCache() {
        this(1000);
    }

    public LRUCache(int maxCapacity) {
        super(16, 0.75F, true);
        this.lock = new ReentrantLock();
        this.maxCapacity = maxCapacity;
    }

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return this.size() > this.maxCapacity;
    }

    public boolean containsKey(Object key) {
        boolean var2;
        try {
            this.lock.lock();
            var2 = super.containsKey(key);
        } finally {
            this.lock.unlock();
        }

        return var2;
    }
    ...
    
  // 也是比较简单的，就是因为hashmap是非线程安全的，所以在操作的时候都加了锁，保证了线程安全性。