LRU 算法

前言

我们常用缓存提升数据查询速度,由于缓存(内存)容量有限,当缓存容量到达上限,就需要删除部分数据腾出空间,这样我们才可以将新的数据加入进来,但是缓存数据又不能随机删除,我们必须根据某种算法来删除,其中 LRU 就是一种常用的数据淘汰算法,下面我们来简单的介绍它。

LRU 简介

LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的数据淘汰算法,这种算法认为最近使用的数据都是热点数据,下一次很大概率也会被使用,未被使用的在未来很大概率也不会被使用。在实际开发过程中,我们常常使用 LRU 作为缓存的淘汰算法。

LRU 缓存实现原理

先定义好数据结构,这里我们选择 Map 作为数据存储结构,因为要想要快速获取数据(最快的时间复杂度是 O(1)), 我们可以选择数组或 Map(哈希表),其实数组也算是一种特殊的 Map,这里我们选择 Map 作为要实现的缓存数据存储结构,但是这个缓存结构是有大小限制的,否则等到数据一多,内存会被撑爆。所以我们还需要另外一种数据结构双向链表来记录数据的访问顺序,最近访问(包含插入)的数据放在链表头,存储满了删除结尾的节点,这个双向链表结构有两个指针,一个操作链表的头,另一个指针操作链表的尾,定义的头指针指向的数据是当缓存满的时候即将要淘汰的数据,定义的尾指针指向的数据是刚刚已经访问过的数据(即插入或访问),有了这两个指针,我们就可以快速操作头和尾,并且把最近使用和最近未使用的数据隔离开来。

图解数据结构