LRU缓存淘汰算法
LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
双向链表实现LRU
将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表尾的位置,新加入的Cache直接加到链表尾。
这样,在多次操作后,最近被访问(get/put)的,就会被向链表尾方向移动,而没有访问的,向链表前方移动,链表头则表示最近最少使用的Cache。
当达到缓存容量上限时,链表头就是最少被访问的Cache,我们只需要删除链表头便可继续添加新的Cache。
代码实现
1 | type Node struct { |