Least Recently Used , 最近最少使用，是一种常用的算法。
LRUCache 是具有一定数量限制的数据结构，该数据结构采用 LRU 算法，维护一定数量的缓存数据。如果数据结构已经达到了最大数量限制时，有新的数据插入，则就需要根据 LRU 算法，删除最久未使用的数据。
根据它的算法特性，常见的实现思路是：
-
根据每次删除最后一个元素的特性，可以优先考虑链表结构 -
如果集合中已存在要添加的元素，优先将其移动到队头，优先考虑链表结构，因为数组的移动开销更大。 -
每次添加新元素都要查询一遍集合中是否存在该元素，链表结构相比数组的查询时间复杂度更高，所以优先考虑数组和查询时间复杂度低的 Map 。
综合前两点考虑，LinkedList 是一个不错的选择，它不光可以是链表结构、还实现了 Deque ，也可以视为队列、栈结构。
而结合最后一点考虑，LinkedHashMap 则是不二之选。
LinkedHashMap
LinkedHashMap 是 Map 接口的散列表和链表实现，具有可预测的迭代顺序。此实现与 HashMap 的不同之处在于它维护一个双向链表，该列表串联起了所有元素。 这个链表定义了迭代顺序，通常是键插入映射的顺序（插入顺序）。
请注意，如果将键重新插入到 Map 中，则插入顺序不会受到影响。（如果在调用 m.containsKey(k) 时调用 m.put(k, v) 将在调用之前立即返回 true，则将键 k 重新插入到映射 m 中。）
内部的双向链表结构：
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
每次访问后会更新链表中的元素顺序：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
核心的排序逻辑在 afterNodeAccess 中：
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; // last
}
tail = p;
++modCount;
}
}
所以这是一种十分适合 LRUCache 的数据结构，Android 中的 LRUCache 就是通过 LinkedHashMap 来实现的。
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
//...
}
LruCache 源码分析
LruCache 中有两个核心方法，get 和 put ，再加上容量变化处理方法，构成了完善的 LRU 机制。
get
get 方法根据 key 检索 LinkedHashMap 中是否存在对应的元素，或者是否可以根据 create 方法创建元素。如果存在或可根据 create 方法创建，则将这个元素移动到队列头部，否则返回 null。
public final V get(K key) {
// key 空检查
if (key == null) {
throw new NullPointerException("key == null");
}
//
V mapValue;
synchronized (this) {
mapValue = map.get(key); // 从 map 中读取元素，
if (mapValue != null) {
hitCount++;
return mapValue; // 读取到直接返回
}
missCount++;
}
V createdValue = create(key); // create 默认返回 null
if (createdValue == null) {
return null;
}
// 当自定义 LRU 实现了 create 执行后续逻辑
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue); // 存入新的元素，并获取前一个 key 对应的值。
if (mapValue != null) {
// 发生碰撞，重置为前一个值
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue); // + 1
}
}
// key 已存在于 map 中
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue; //返回最新插入的已存在的元素
} else {
trimToSize(maxSize); // 扩容
return createdValue; //返回最新插入的元素
}
}
这里的 create 方法默认返回 null , 供子类实现:
protected V create(K key) {
return null;
}
最后的 entryRemoved 方法的作用是，对当缓存达到最大数量时被移除的对象或被直接移除的对象进行处理逻辑。
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
方法中的两个参数的含义：
-
evicted – 如果条目被删除以腾出空间，则为 true，如果删除是由 put 或 remove 引起的，则为 false。 -
newValue – 键的新值（如果存在）。如果非 null，则此移除是由 put 或 get 引起的。否则，它是由驱逐或移除引起的。
那么问题来了，get 方法使用了元素，它的重新排序在哪里呢？答案是 LinkedHashMap 的 get 方法将元素移动到了队尾。
trimToSize
容量处理伴随着删除最久未使用的元素，即驱逐：
// 删除最老的元素，直到剩余元素的总数等于或低于请求的大小。
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}
if (size <= maxSize) {
break;
}
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
在这个方法中，通过 map.eldest() 获取到了存活最久的元素，它的实现是：
// in LinkedHashMap
public Map.Entry<K, V> eldest() {
return head;
}
put
LRUCache 的 put 方法用来更新数据，put
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value); // 扩容 + 1
previous = map.put(key, value); // key 先前关联的 value
if (previous != null) {
size -= safeSizeOf(key, previous); // map 中已存在 key 的情况下，保证 size 不变
}
}
// 先前存在元素，执行元素移除后的自定义操作
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 容量处理
trimToSize(maxSize);
return previous;
}
这里也有一个问题，如果 map 中已存在 key ，仅是更新数据，这里没有涉及到排序的问题。
为什么这么说呢？是因为 LinkedHashMap 并没有定义 put 方法，需要向上查看 HashMap 中的 put 方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
HashMap 中的 put 方法中真正逻辑是 putVal 方法，在 putVal 方法中调用了访问元素后的处理方法 afterNodeAccess 方法，而这个方法的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// ...
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 【*】
return oldValue;
}
// ...
}
afterNodeAccess 方法在 HashMap 中是空实现，通过备注可以理解，这是一个专门为 LinkedHashMap 预留的方法：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
而 afterNodeAccess 在 LinkedHashMap 中的实现，和 LinkedHashMap 的 get 方法中调用的排序方法是同一个。所以 put 方法也会对元素进行排序。
总结
android.util.LruCache 类是一个 LRU 缓存实现，它的内部数据结构采用的是 LinkedHashMap 。
LinkedHashMap 实现了 HashMap ，并且维护了一个双端链表来处理元素的排序。
核心的排序逻辑在 afterNodeAccess 方法中，当超过容量限制时，会删除链表中 head 节点。每次访问数据，会将节点更新到队尾。
android.util.LruCache 提供了一些方法供用户自行实现，从而能够实现自定义的 LruCache 。
Other
最后再来聊一下字节面试频率比较高的一道算法题，实现一个 Lru ，思路基本上是通过一个 哈希表 + 一个 双向链表 来实现。
class LRUCache(private val capacity: Int) {
data class DLinkedNode(
var key: Int? = null,
var value: Int? = null,
var prev: DLinkedNode? = null,
var next: DLinkedNode? = null
)
private val cache = HashMap<Int, DLinkedNode>()
private var size = 0
private var head = DLinkedNode()
private var tail = DLinkedNode()
fun get(key: Int): Int {
val node = cache[key] ?: return -1
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node)
return node.value ?: -1
}
fun put(key: Int, value: Int) {
val node = cache[key]
if (node == null) {
// 如果 key 不存在，创建一个新的节点
val newNode = DLinkedNode(key, value)
// 添加进哈希表
cache[key] = newNode
// 添加至双向链表的头部
addToHead(newNode)
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
val tail = removeTail()
// 删除哈希表中对应的项
cache.remove(tail?.key)
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private fun addToHead(node: DLinkedNode?) {
node?.prev = head
node?.next = head.next
head.next?.prev = node
head.next = node
}
private fun removeNode(node: DLinkedNode?) {
node?.prev?.next = node?.next
node?.next?.prev = node?.prev
}
private fun moveToHead(node: DLinkedNode?) {
removeNode(node)
addToHead(node)
}
private fun removeTail(): DLinkedNode? {
val res = tail.prev
removeNode(res)
return res
}
}
时间复杂度：对于 put 和 get 都是 O(1) 。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity + 1 个元素。
原文始发于微信公众号（八千里路山与海）：Java 中的 LruCache
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/60277.html
