lru全称是least recently used，即最近最少使用。该算法一般应用于内存缓存场景，提供了在缓存数据规模增大时限制数据集合大小，优先保留热点数据的方案。lru在数据规模到达集合上限时会优先清理上次访问时间距当前最久的数据，这样的好处在于能够保证热点数据更长时间驻留，有利于提供系统的整体访问性能，减少从外存或磁盘读取数据的次数。

LinkedHashMap

JDK自带集合工具中已经为我们提供了lru算法的解决方案，即LinkedHashMap。LinkedHashMap继承于HashMap，在原有hash数组的基础上追加了一个双向链表结构。我们知道，数组长于随机访问，短于增删数据，而链表正好相反，增删数据方便，但只能顺序访问。因此，这里其实结合了数组和链表各自的优势，实现高效的随机访问和元素增删，典型的空间换时间。

LinkedHashMap比HashMap多出两个私有属性。首先是布尔型的accessOrder，当其为true，则当前为lru算法模式，否则为传统模式，即按照插入顺序遍历读取。其次是header，作为链表的头节点构建链表。

header的声明类型Entry继承自HashMap的Entry，其主要实现逻辑是覆写了recordAccess方法，我们来看下源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}
private void remove() {
    before.after = after;
    after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

当accessOrder设置为true，则将当前访问节点首先从原来位置移除，然后置为头节点。这一系列操作实现将最近访问的节点移动到头部，保证了在达到容量上限需要移除元素时能够最后被移除。因此，这里也是实现lru算法的核心逻辑。

在查询或插入时，会执行recordAccess方法进行访问元素位置的调整。特别的是，插入时执行父类方法put，然后执行子类重写的recordAccess方法进行元素调整，是一个模板方法模式。另外LinkedHashMap重写了addEntry方法，这个算是对HashMap逻辑的覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
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;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

这里createEntry将元素加入链表头部。然后检查是否需要删除最老的元素，存在两个问题：一是header.after表示的是链表尾部，这是双向链表的环形结构决定的；二是removeEldestEntry是一个空的实现，默认返回false。在使用时需要我们覆写逻辑,以决定什么时候可以进行老旧数据的删除逻辑。一个简单的实现如下:

1
2
3
4
5
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

小结

以上是对LinkedHashMap实现lru的一个简单源码分析。虽然简单，但其设计思想还是很值得借鉴的，没有时间戳，没有版本号，通过简单的链表节点的位置移动即可实现对数据访问时间的排序，保证了整体的访问速度。