LinkedHashMap原理以及LRU缓存算法相关

和宝马X6比，流线型还是差一点

雷克萨斯NX

和hashmap相比，linkedhashmap是有序的，顺序方式两种，插入顺序和访问顺序，而后面要说的lru就是借助了访问顺序的linkedhashmap实现。

使用：

Lru<Character, Integer> lru = new Lru<Character, Integer>(16, 0.75f, true);
String s = "1234567";
for (int i = 0; i < s.length(); i++) {
lru.put(s.charAt(i), i);
}
System.out.println("第三个是： " + lru.get('2'));
System.out.println("大小：" + lru.size());
System.out.println("LRU ：" + lru);

输出：

第三个是： 3
大小：6
LRU ：{1，2，4，5，6，3}

accessorder构造方法第三个参数，默认为false。是否按照访问顺序排序。

这里要注意的一点，linkedhashmap构造方法的第三个参数 accessorder = true。按照访问顺序排序，从例子中可以看到，插入顺序123456，而经过一次访问get("2")之后，那么顺序变为124563。这就是accessorder的特性。

源码分析：

linkedhashmap继承hashmap，下面是关键的两个成员变量，accessorder上面给出解释。

private transient Entry<K,V> header;
private final boolean accessOrder;

private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
}

上面源码看，重写了hashmap的entry，结点多了前驱结点和后续结点，很明显采用了双向链表。
再来看一下put方法。

public V put(K key, V value) {
//省略
addEntry(hash, key, value, i);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
// 如果超过一定数量，删除最近没有使用的，也就是头结点的下一个结点。
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
         removeEntryForKey(eldest.key);
}
else {
         if (size >= threshold)
             resize(2 * table.length);
}
}

核心就在当注释，比如设置的是100个数量，那么当达到100，就会删除最近最少使用。

再来看一下get方法。

public V get(Object key) {
     Entry<K,V> e = (Entry<K,V>)getEntry(key);
     if (e == null)
     return null;
     e.recordAccess(this);
     return e.value;
}
     void recordAccess(HashMap<K,V> m) {
         LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
         if (lm.accessOrder) {//如果为true，则按照访问排序
             lm.modCount++;
             remove();//删除当前访问的结点
             addBefore(lm.header);//再把当前结点加入到尾部
}
}

private void addBefore(Entry<K,V> existingEntry) {
     after = existingEntry;//设置后续结点
     before = existingEntry.before;//设置前驱结点
     before.after = this; //设置前驱结点的后续结点
     after.before = this; }//设置后续结点的前驱结点

在get中调用addbefore传入header头结点，四行代码的意思
设置当前访问结点的后续结点为头结点，
设置当前访问结点的前驱结点为之前头结点的前驱结点(也就是之前最后一个结点)
设置前驱结点(头结点)的后续结点为当前结点。
设置后续结点的前驱为当前结点。
这是双向链表增加元素的一般步骤。

所以到这里，开头的例子为什么get之后就改变了顺序原因就明白了。

LRU算法

void addEntry(int hash, K key, V value, int bucketIndex) {
     createEntry(hash, key, value, bucketIndex);
     // Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
     //如果removeEldestEntry方法返回为true，那么则删除1个节点
     //默认就是删除离header节点最近的节点，即header的after，即链表的头部
     if (removeEldestEntry(eldest)) {
     removeEntryForKey(eldest.key);
     }
    else {
         if (size >= threshold)
             resize(2 * table.length);
     }
}

默认removeeldestentry()返回的是false，想要使用lru，重写，返回true。那么每次都是删除header的下一个结点。