如何在 Java 中实现 LRU 缓存
1. 概述
LRU(Least Recently Used,最近最少使用)缓存是一种常用的缓存策略,它根据数据的访问时间来管理缓存,将最近访问过的项目保留在缓存中,而将最久未访问的项目淘汰。
核心思想:
- 优先级: 最近使用过的项目被认为更可能被再次使用,因此优先保留。
- 淘汰策略: 最久未使用的项目被认为最不可能再次使用,因此被淘汰。
优点:
- 有效利用内存: 缓存有限的空间,只存储最近使用的项目,避免浪费空间。
- 提升性能: 减少访问数据的延迟,提升数据访问速度。
缺点:
- 需要额外的空间和时间开销: 需要维护访问顺序,会增加一些额外的时间和空间开销。
- 不适合所有场景: 如果项目被访问的概率比较均匀,LRU 缓存可能不如其他缓存策略有效。
2. LRU缓存
最近最少使用 (LRU) 缓存是一种按使用顺序组织元素的缓存驱逐算法。顾名思义,在 LRU 中,最长时间未使用的元素将从缓存中驱逐。
例如,如果我们有一个容量为三个项目的缓存:
最初,缓存为空,我们将元素 8 放入缓存中。元素 9 和 6 像以前一样被缓存。但现在,缓存容量已满,要放入下一个元素,我们必须逐出缓存中最近最少使用的元素。
在我们用 Java 实现 LRU 缓存之前,最好先了解有关缓存的一些方面:
- 所有操作应按 O(1) 顺序运行
- 缓存大小有限
- 所有缓存操作必须支持并发
- 如果缓存已满,添加新项目必须调用 LRU 策略
2.1. LRU 缓存的结构
现在,我们来思考一个有助于我们设计缓存的问题。
我们如何设计一个数据结构,可以在恒定时间内执行读取,排序(时间排序)和删除元素等操作?
看来要找到这个问题的答案,我们需要深入思考有关 LRU 缓存及其特性的论述:
- 实际上,LRU 缓存是一种队列——如果某个元素被重新访问,它将进入驱逐顺序的末尾
- 由于缓存的大小有限,因此此队列将具有特定的容量。每当引入新元素时,都会将其添加到队列的头部。当发生驱逐时,它会从队列的尾部进行。
- 必须在恒定时间内访问缓存中的数据,这在队列中是不可能的!但是,使用 Java 的[HashMap]数据结构就可以实现
- 删除最近最少使用的元素必须在恒定时间内完成,这意味着对于Queue的实现,我们将使用*[DoublyLinkedList]而不是[SingleLinkedList]或数组
因此,LRU 缓存不过是DoublyLinkedList和HashMap的组合,如下所示:
这个想法是将键保存在Map上 ,以便快速访问Queue内的数据。
2.2. LRU 算法
LRU 算法非常简单!如果键存在于HashMap 中, 则为缓存命中;否则,为缓存未命中。
发生缓存未命中后,我们将执行两个步骤:
- 在列表前面添加一个新元素。
- 在HashMap中添加新条目并引用列表的头部。
并且,缓存命中后我们将执行两个步骤:
- 删除命中元素并将其添加到列表前面。
- 使用对列表前面的新引用来更新HashMap 。
现在,是时候看看如何在 Java 中实现 LRU 缓存了!
3. Java 实现
首先,我们定义我们的Cache接口:
public interface Cache<K, V> {
boolean set(K key, V value);
Optional<V> get(K key);
int size();
boolean isEmpty();
void clear();
}
现在,我们将定义代表缓存的LRUCache类:
public class LRUCache<K, V> implements Cache<K, V> {
private int size;
private Map<K, LinkedListNode<CacheElement<K,V>>> linkedListNodeMap;
private DoublyLinkedList<CacheElement<K,V>> doublyLinkedList;
public LRUCache(int size) {
this.size = size;
this.linkedListNodeMap = new HashMap<>(maxSize);
this.doublyLinkedList = new DoublyLinkedList<>();
}
// rest of the implementation
}
我们可以创建一个具有特定大小的LRUCache 实例。在此实现中,我们使用HashMap集合来存储对 LinkedListNode的所有引用。
现在,让我们讨论一下LRUCache上的操作。
3.1. Put 操作
第一个是put方法:
public boolean put(K key, V value) {
CacheElement<K, V> item = new CacheElement<K, V>(key, value);
LinkedListNode<CacheElement<K, V>> newNode;
if (this.linkedListNodeMap.containsKey(key)) {
LinkedListNode<CacheElement<K, V>> node = this.linkedListNodeMap.get(key);
newNode = doublyLinkedList.updateAndMoveToFront(node, item);
} else {
if (this.size() >= this.size) {
this.evictElement();
}
newNode = this.doublyLinkedList.add(item);
}
if(newNode.isEmpty()) {
return false;
}
this.linkedListNodeMap.put(key, newNode);
return true;
}
首先,我们在存储所有键/引用的linkedListNodeMap中找到键。如果该键存在,则发生缓存命中,并且准备从DoublyLinkedList中检索 CacheElement并将其移至最前面 。
之后,我们用新的引用更新linkedListNodeMap并将其移动到列表的前面:
public LinkedListNode<T> updateAndMoveToFront(LinkedListNode<T> node, T newValue) {
if (node.isEmpty() || (this != (node.getListReference()))) {
return dummyNode;
}
detach(node);
add(newValue);
return head;
}
首先,我们检查节点是否为空。此外,节点的引用必须与列表相同。之后,我们将节点从列表中分离出来,并将 newValue添加到列表中。
但是如果该键不存在,则会发生缓存未命中,我们必须将新键放入 linkedListNodeMap 中 。 在执行此操作之前,我们会检查列表大小。如果列表已满,我们必须从列表中逐出最近最少使用的元素。
3.2. 获取操作
我们来看看我们的获取操作:
public Optional<V> get(K key) {
LinkedListNode<CacheElement<K, V>> linkedListNode = this.linkedListNodeMap.get(key);
if(linkedListNode != null && !linkedListNode.isEmpty()) {
linkedListNodeMap.put(key, this.doublyLinkedList.moveToFront(linkedListNode));
return Optional.of(linkedListNode.getElement().getValue());
}
return Optional.empty();
}
如上所示,此操作非常简单。首先,我们从linkedListNodeMap中获取节点,然后检查它是否为 null 或为空。
其余操作与以前相同,只有moveToFront方法有一个区别:
public LinkedListNode<T> moveToFront(LinkedListNode<T> node) {
return node.isEmpty() ? dummyNode : updateAndMoveToFront(node, node.getElement());
}
现在,让我们创建一些测试来验证我们的缓存是否正常工作:
@Test
public void addSomeDataToCache_WhenGetData_ThenIsEqualWithCacheElement(){
LRUCache<String,String> lruCache = new LRUCache<>(3);
lruCache.put("1","test1");
lruCache.put("2","test2");
lruCache.put("3","test3");
assertEquals("test1",lruCache.get("1").get());
assertEquals("test2",lruCache.get("2").get());
assertEquals("test3",lruCache.get("3").get());
}
现在,让我们测试一下驱逐政策:
@Test
public void addDataToCacheToTheNumberOfSize_WhenAddOneMoreData_ThenLeastRecentlyDataWillEvict(){
LRUCache<String,String> lruCache = new LRUCache<>(3);
lruCache.put("1","test1");
lruCache.put("2","test2");
lruCache.put("3","test3");
lruCache.put("4","test4");
assertFalse(lruCache.get("1").isPresent());
}
4. 处理并发
到目前为止,我们假设我们的缓存仅在单线程环境中使用。
为了使这个容器线程安全,我们需要同步所有公共方法。让我们在前面的实现中添加一个[ReentrantReadWriteLock]和[ConcurrentHashMap :]
public class LRUCache<K, V> implements Cache<K, V> {
private int size;
private final Map<K, LinkedListNode<CacheElement<K,V>>> linkedListNodeMap;
private final DoublyLinkedList<CacheElement<K,V>> doublyLinkedList;
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
public LRUCache(int size) {
this.size = size;
this.linkedListNodeMap = new ConcurrentHashMap<>(size);
this.doublyLinkedList = new DoublyLinkedList<>();
}
// ...
}
我们倾向于使用可重入读/写锁,而不是将方法声明为[同步, ]因为它为我们提供了更多灵活性来决定何时对读写使用锁。
4.1.写锁
现在,我们在put方法中添加对 writeLock的调用:
public boolean put(K key, V value) {
this.lock.writeLock().lock();
try {
//..
} finally {
this.lock.writeLock().unlock();
}
}
当我们对资源使用writeLock时,只有持有锁的线程才能写入或读取资源。因此,所有其他试图读取或写入资源的线程都必须等待,直到当前锁持有者释放它。
这对于防止 [死锁非常重要。如果]try块内的任何操作失败,我们仍然会在方法末尾使用finally块在退出函数之前释放锁。
需要writeLock 的其他操作是evictElement,我们在put方法中用到了它:
private boolean evictElement() {
this.lock.writeLock().lock();
try {
//...
} finally {
this.lock.writeLock().unlock();
}
}
4.2.读锁
现在是时候向get方法添加 readLock调用了:
public Optional<V> get(K key) {
this.lock.readLock().lock();
try {
//...
} finally {
this.lock.readLock().unlock();
}
}
这看起来和我们使用put方法所做的完全一样。唯一的区别是我们使用readLock而不是writeLock。因此,读写锁之间的区别使我们能够在缓存未被更新时并行读取缓存。
现在,让我们在并发环境中测试我们的缓存:
@Test
public void runMultiThreadTask_WhenPutDataInConcurrentToCache_ThenNoDataLost() throws Exception {
final int size = 50;
final ExecutorService executorService = Executors.newFixedThreadPool(5);
Cache<Integer, String> cache = new LRUCache<>(size);
CountDownLatch countDownLatch = new CountDownLatch(size);
try {
IntStream.range(0, size).<Runnable>mapToObj(key -> () -> {
cache.put(key, "value" + key);
countDownLatch.countDown();
}).forEach(executorService::submit);
countDownLatch.await();
} finally {
executorService.shutdown();
}
assertEquals(cache.size(), size);
IntStream.range(0, size).forEach(i -> assertEquals("value" + i,cache.get(i).get()));
}
5. 结论
在本教程中,我们了解了 LRU 缓存到底是什么,包括它的一些最常见的功能。然后,我们了解了一种在 Java 中实现 LRU 缓存的方法,并探索了一些最常见的操作。 LRU 缓存广泛应用于各种场景,例如:
- 网页缓存: 存储最近访问过的网页内容,减少网络请求,提高网页加载速度。
- 数据库缓存: 存储最近查询过的数据,避免重复查询数据库,提升查询效率。
- 图片缓存: 存储最近查看过的图片,减少图片加载时间,提升用户体验。
- 游戏开发: 缓存游戏资源(例如模型、纹理), 减少加载时间,提高游戏流畅度。
转载自:https://juejin.cn/post/7391746098682429478