LRU(缓存淘汰算法)高速缓存

优点：超快速访问、超快速更新。

缺点：空间笨重

LRU驱逐：

缓存容量固定，最近使用的数据是有用的，很久没有使用的数据是无用的，缓存满了后优先删除那些很久没有使用的数据。

1.请求巧克力，放入缓存第一位。
2.请求香草，放入缓存第一位，巧克力为第二位。
3.请求草莓，放入缓存第一位，香草第二位，巧克力第三位。
4.请求巧克力，放入第一位，状态为多次访问。草莓第二位，香草第三位。
5.请求磅，放入第一位，将访问次数最少的香草踢出，巧克力第二位，草莓第三位。

LRU缓存实施：

LRU缓存通常是通过将双链表与哈希映射表配对来实现的(哈希链表)。借助哈希表赋予了链表快速查找的特性：可以快速查找某个key是否在缓存(链表)中，同时可以快速删除，添加节点。

访问和逐出：

在我们的哈希表映射查找该条目，如果该项目在哈希表中，那么它已经在我们的缓存中了，这称为缓存命中。使用哈希表可以快速找到相应的链表节点，将项目的链表节点移到链表的头部，因为它是最近使用过的。

如果项目不在哈希表中，则我们有一个”缓存空缺”。我们需要将该条目加载到缓存中，如果缓存已满，则需要腾出一些空间。找到最近最少使用的缓存项，它将位于链接列表的末尾。通过从链接列表和哈希图中删除该项目，可以从缓存中逐出该项目。如果缓存未满，为该项目创建一个新的链接列表节点。将其插入到链接列表的开头。将项目添加到我们的哈希图中，将新创建的链表节点存储为值。