系统设计主题6：LRU缓存

在本主题中，我们将了解LRU缓存及其在系统设计中的重要性。

LRU用于驱逐高速缓存。高速缓存逐出是一个过程，在该过程中，存储的高速缓存将在达到特定限制时被释放。有许多用于驱逐缓存的算法，例如LRU–最近最少使用的FIFO–先进先出，后进先出–TLRU后进先出–时间感知最近最少使用。在那些LRU中，更常用的一种。

在逐出缓存期间，要删除的项目非常重要。您不能删除最近使用的项目，也不能删除经常使用的最常用的项目。

LRU代表“最近最少使用”。该策略规定，如果在删除缓存时达到缓存限制，则会删除使用最少的项目。

如何执行呢？

LRU由双链表（DLL）和哈希表实现。

因此，在我们的示例中，HashMap中有6个DLL节点和6个值。 DLL用于存储缓存值。每当有新的缓存时，它将存储在前面，这样最少使用的将存储在后面。

在插入一个新值时，我们将首先检查DLL，如果有一个与新值匹配的值，那么我们将在开始时移动该节点。否则，新值将插入到开头。

但是为什么我们需要HashMap？

为了在DLL中搜索值，将花费O（n）时间。因此，为了减少时间复杂度，我们使用HashMap。因此，通过使用HashMap，我们可以在恒定时间O（1）中进行搜索。

因此，当缓存已满时，我们将删除DLL的最后一个节点，并将新项移动到链表的开头。

该网站上可用的教程列表：