LinkedHashMap实现的LRU算法源码分析

我们知道，通过LinkedHashMap中accessOrder=true的构造函数，可以创建实现LRU算法Map，那在Java内部是怎样实现的呢？ 大概看了下源码(JDK8)，记录下。

首先从构造函数开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

accessOrder字段是final的且没有初始值，只能在构造函数中赋值，也就是说实例化之后，不能再次改变access-order或insertion-order

通过eclipse open call hierarchy, 查看accessOrder字段被哪些方法引用，需要注意的只有1个方法: java.util.LinkedHashMap.afterNodeAccess(Node<K, V>)

这个就是实现LRU的核心算法, 来看下方法体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
}

只是一个很简单的双链表操作

afterNodeAccess方法会被get, put, replace这些方法调用, 也就是说每次access之后, 被access的那个元素会被移动到末尾。
以get为例子

1
2
3
4
5
6
7
8
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;
}

够简单的吧 ！

上面讲到的只是LRU算法中的排序部分，至于元素的移除更简单, 只需要在put或merge时判断
调用链是这样的: put->putVal->afterNodeInsertion->removeEldestEntry， 我们要做的只需要override removeEldestEntry

1
2
3
4
@Override
protected boolean removeEldestEntry(Entry<Object, Object> eldest) {
    return (size() > 100);
}

简单的数据结构加上精妙的算法，实现了简洁而实用的缓存。在JDK源码中，这样的经典实现还有很多。