LeetCode进阶-实战之LRU缓存机制（阿里面试题）

闲聊

最近github上有个很火的面试相关的项目短短几天时间就进入了trending首页，项目是关于国内几家互联网大公司的面试题以及答案，里面有不少算法题都值得刷一刷。本篇主要讲阿里面试题里面的LRU缓存机制，github上附有答案，遗憾的是只有python版和C++版本的，没有Java版本的...无fuck说，Java可是世界排名第一的语言！！！

阿里面试题-LRU缓存机制

LRU 缓存机制设计和实现一个 LRU（最近最少使用）缓存数据结构，使它应该支持一下操作：get 和 put。 get(key) - 如果 key 存在于缓存中，则获取 key 的 value（总是正数），否则返回 -1。 put(key,value) - 如果 key 不存在，请设置或插入 value。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

为什么要刷LeetCode？

LRU是Least Recently Used的缩写，即最近最少使用。根据题意需要手写一个LRU算法，事实上在LeetCode上搜LRU便可以搜到146. LRU Cache，对比下面试题是一摸一样。为了方便结果验证，我们直接来看LeetCode原题。

原题

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4

146. LRU缓存

设计和实现一个LRU(最近最少使用)的缓存机制。它可以支持以下操作： get 和 put 。

获取数据 get(key) - 如果 (key) 存在于缓存中，则获取值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果key不存在，则写入其数据值。当缓存容量达到上限时，在写入新数据之前删除最近最少使用的数据，从而为新的数据留出空间。

进阶:

你能否在 O(1) 时间复杂度内完成？

例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得key 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得key 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4

本题在LeetCode上在Design分类下

方法一：双向链表队列实现LRU

思路设计

考虑到题目中的最近最少,我们显然能联想到使用队列结构。结合题意，为了尽可能的提高插入和查找的效率，保证时间复杂度在O(1)，最大程度的提高get和put的速度，必然要使用双向链表队列（单链表需要遍历才能插入节点，时间复杂度高）。而在实现了双向链表队列结构之后还需要考虑两点：1、插入数据put达到数量上限时，删除最老节点（最长时间未被使用），即链表队列的尾部节点，因为尾部节点是最晚插入的；2、获取数据get到数据时，需要将当前获取到的节点移动到队列头部，因为最近被使用了。

编码实践

public class LRUCache {
	/**
	 * 
	 * Node类用于抽象链表的节点
	 * key、value存储键、值，
	 * before、after分别指向当前节点的前后Node节点；
	 *
	 */
	class Node {
		int key;
		int value;
		Node before;
		Node after;
	}
	
	/**
	 * 使用HashMap缓存Node节点
	 */
	private HashMap<Integer, Node> cache = new HashMap<Integer, Node>();
	/**
	 * 最大容量，超过capacity时继续插入会触发删除最老未被使用的节点
	 */
	private int capacity;
	/**
	 * 头节点、尾节点（注意这两个节点不存储实际的数据）
	 */
	private Node head, tail;

	public LRUCache(int capacity) {
		this.capacity = capacity;

		head = new Node();
		head.before = null;

		tail = new Node();
		tail.after = null;

		head.after = tail;
		tail.before = head;
	}

	/**
	 * 将节点插入队列头部
	 * 
	 * @param node
	 */
	private void addToHead(Node node) {

		node.before = head;
		node.after = head.after;
		head.after.before = node;
		head.after = node;

	}

	/**
	 * 删除队列中的一个节点
	 * 
	 * @param node
	 */
	private void removeNode(Node node) {
		Node before = node.before;
		Node after = node.after;
		before.after = after;
		after.before = before;
	}

	/**
	 * 将节点移动到有效数据头部
	 * 
	 * @param node
	 */
	private void moveToHead(Node node) {
		removeNode(node);
		addToHead(node);
	}

	/**
	 * 删除有效数据尾节点
	 * 
	 * @return 尾节点
	 */
	private Node popTail() {
		Node res = tail.before;
		this.removeNode(res);
		return res;
	}

	public int get(int key) {
		Node node = cache.get(key);
		if (node == null) {
			return -1; // should raise exception here.
		}
		// 如果获取到数据，则将获取到的节点移动到队列头部;
		moveToHead(node);
		return node.value;
	}

	public void put(int key, int value) {
		Node node = cache.get(key);
		if (node == null) {
			Node newNode = new Node();
			newNode.key = key;
			newNode.value = value;
			cache.put(key, newNode);
			addToHead(newNode);
			if (cache.size() > capacity) {
				// 删除队尾有效数据节点
				Node tail = this.popTail();
				this.cache.remove(tail.key);
			}
		} else {
			node.value = value;
			// 在使用get方法获取值之后，需要将当前获取的节点移动到队列头部
			moveToHead(node);
		}
	}
}

说明

见代码注释

方法二：Java标准库JDK里的LinkedHashMap

思路

事实上Java标准库里提供了可以直接使用的LRU思想的数据结构，即LinkedHashMap，其底层实现原理和方法一是一致的

编码实践

class LRUCache extends LinkedHashMap<Integer,Integer>  {
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F,true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {
        super.put(key,value);
    }
    
    @Override 
    public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
        return size() > capacity;
    }
}

说明

LinkedHashMap提供了可以覆写的removeEldestEntry方法，removeEldestEntry方法的作用直接参考LinkedHashMap源码：

  /**
     * Returns <tt>true</tt> if this map should remove its eldest entry.
     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
     * inserting a new entry into the map.  It provides the implementor
     * with the opportunity to remove the eldest entry each time a new one
     * is added.  This is useful if the map represents a cache: it allows
     * the map to reduce memory consumption by deleting stale entries.
     *
     * <p>Sample use: this override will allow the map to grow up to 100
     * entries and then delete the eldest entry each time a new entry is
     * added, maintaining a steady state of 100 entries.
     * <pre>
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() &gt; MAX_ENTRIES;
     *     }
     * </pre>
     *
     * <p>This method typically does not modify the map in any way,
     * instead allowing the map to modify itself as directed by its
     * return value.  It <i>is</i> permitted for this method to modify
     * the map directly, but if it does so, it <i>must</i> return
     * <tt>false</tt> (indicating that the map should not attempt any
     * further modification).  The effects of returning <tt>true</tt>
     * after modifying the map from within this method are unspecified.
     *
     * <p>This implementation merely returns <tt>false</tt> (so that this
     * map acts like a normal map - the eldest element is never removed).
     *
     * @param    eldest The least recently inserted entry in the map, or if
     *           this is an access-ordered map, the least recently accessed
     *           entry.  This is the entry that will be removed it this
     *           method returns <tt>true</tt>.  If the map was empty prior
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
     *           in this invocation, this will be the entry that was just
     *           inserted; in other words, if the map contains a single
     *           entry, the eldest entry is also the newest.
     * @return   <tt>true</tt> if the eldest entry should be removed
     *           from the map; <tt>false</tt> if it should be retained.
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

大概意思是在新插入一个节点时，删除最老的节点，在缓存数据时可以用到（简直是LRU思想的量身定做）。另外如果使用默认false的话，表示容器没有限制大小，不删除最老未被使用的节点，相当于使用普通的Map。

还可以注意到注释中有一段很醒目的demo写法：

	 private static final int MAX_ENTRIES = 100;
	    
     protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() &gt; MAX_ENTRIES;
     }

本题中由于限制条件为超过队列最大值限制大小即开始删除最老节点，因此使用size() > capacity判断条件。注意到get方法不是直接调用而是使用的getOrDefault(key,-1)是由于题目描述当get拿不到数据时默认返回-1。

彩蛋

观察方法一手写双向链表的实现，addToHead将节点添加到头部方法以及popTail删除尾节点的方法，分别是添加节点到头部第二个节点，以及删除倒数第二个节点，这是为什么呢？这便是本篇的彩蛋。

结语

针对阿里的LRU面试题，本题分析了两种解法。个人猜测阿里出题者的出题思路是考察LRU思想的理解，在理解思想的基础上可能会进一步延伸到LinkedHashMap的源码，LinkedHashMap熟悉了会假装不经意继续深入到它的父类HashMap，到了HashMap肯定继续会问你负载因子，Hash碰撞，红黑树裂变，左右旋扯完了HashMap再和你谈谈HashTable和区别...你会发现总有一处可能命中你的盲点，是不是细思极恐，哈哈～不要方，扫一扫，关注我的微信订阅号，后续会有针对类似LinkedHashMap等比较重要的数据结构的源码分析系列文章，敬请期待！最后，如果觉得本文对你有所帮助或启发那就来个赞吧0.0

扫一扫关注我的微信订阅号