转载

面试准备 - LinkedHashMap 与 LRU

LRU(Least Recently Used) 最近最少使用，是一种缓存淘汰算法，即最近最少使用, 哪个最近不怎么用了就淘汰掉，根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过，那么将来访问的几率也更高。

那么相对的，不得不提的还有其他两个

LRU (least recently used）) 最近最久未使用 :ok_hand:
FIFO（first in first out）先进先出
LFU（least frequently used）最近最少使用

以上都是「淘汰」策略

源码

再来看看 JDK 中的 linkedHashMap 到底和 LRU 有什么关系，单看名字来说，我认为他也就是 HashMap 的「有序版」，那么和 LRU 有什么关系呢？

文档： docs.oracle.com/javase/8/do…

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches. Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The replace methods only result in an access of the entry if the value is replaced. The putAll method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect the order of iteration of the backing map.

提供了一个特殊的构造函数来创建一个 LinkedHashMap，其迭代的顺序是其条目最后一次被访问的顺序，从最近访问到最近访问(访问顺序)。这种 map 非常适合构建LRU缓存。

怎么算访问？

不是只有 get 才算「访问」，put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge 都算是进行了「访问」。

继续看源码看到了一个 access-order 相关的构造器：

/**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
复制代码

初始容量、负载因子就不说了，accessOrder：true 按访问顺序、false 按插入顺序，默认是 false 的

测试一下

我应该怎样做才能更直观的展现出 LRU 并且写出来呢？

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
	private int size;

	public static void main(String[] args) {
		LRUCache<Integer, Integer> cache = LRUCache.newInstance(3);
		cache.put(1, 1);
		cache.put(2, 2);
		cache.put(3, 3);
		cache.put(4, 4);

		System.out.println(cache);

		cache.get(2);
		System.out.println(cache);

		cache.put(5,5);
		System.out.println(cache);
	}

	private LRUCache(int size) {
		super(size, 0.75f, true);
		this.size = size;
	}

	// 写成子类的意义就是为了重写 removeEldestEntry 「自动删除  head (eldest) 头部的条目」
	@Override
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return size() > size;
	}

	public static <K, V> LRUCache<K, V> newInstance(int size) {
		return new LRUCache<K, V>(size);
	}

}
复制代码

The output is :

{2=2, 3=3, 4=4}
{3=3, 4=4, 2=2}
{4=4, 2=2, 5=5}

Process finished with exit code 0
复制代码

解释一下：

1、我定义了初始长度为 3 、负载因子 0.75、按访问顺序 LRU

2、重写了 removeEldestEntry 超过 size 的头部被清理掉

3、程序本该输出 {1=1, 2=2, 3=3, 4=4}，但是超出 size 了， 1=1 被清理了

4、按照流程 2=2 马上被清理了，但是我 get 访问了一下，他被放在队尾了

5、本来 2 应该被挤掉的，现在链子后面的 3 排队别清理了

得到了我预期的结果

{4=4, 2=2, 5=5}
复制代码

探究实现

抛几点疑问：

linkedHashMap 何时改变的顺序如何实现的

源码：

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

    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;
        }
    }
复制代码

非常易读，就操作了下 next 和 prev 指针，没啥好说的

总结

LinkedHashMap 继承于 HashMap，在原有 hash 数组的基础上追加了一个双向链表结构，既保证了数据的有序性，有在有序的基础上实现了 LRU 算法，LRU 算法一般应用于内存缓存场景，「空间」换「时间」的最佳选择，保证有限的预期长度尽量保留热点数据，数据不在再去使用其他曲涛查询，合理使用确实可以节省 IO 或网络请求。

原文 https://juejin.im/post/5dfb9b85f265da33e97fd4aa

正文到此结束