NingG +

基础原理系列:LRU Cache 原理

1.概述

LRU ,几个方面:

  1. 算法的基本要求
  2. 基本思路
  3. 几个相关实现:HashMapLinkedHashMapConcurrentHashMap,以及底层实现机制

2.LRU 剖析

LRULeast Recently Used,最近最少使用。判断最近被使用的时间,目前最远的数据优先被淘汰。

2.1.基本要求

基本要求:

  1. 一个内存空间:设置缓存空间大小,创建一个空间,空间的大小受传入参数的控制
  2. 支持通用操作getset,时间复杂度都为 O(1)
  3. 支持特殊操作set key 时,如果空间不足,自动失效最久远的 key,时间复杂度为 O(1),实际是覆盖更新

2.2.基本思路

基本思路:

  1. LRU算法是根据数据的访问历史来进行淘汰的,总会优先淘汰哪些最近未被访问活着访问率低的数据。
  2. 其实现过程是建立在链表的基础上的,
    1. 新加入的数据,放在链表的头部,
    2. 当原来链表中的数据被访问时,该数据也会被移到链表头部,
    3. 而那些最近未被访问的数据自然就移到了链表的尾部
    4. 当链表满需要淘汰数据时,就会移除尾部的数据,腾出空间,供新数据插入。

实现过程如图:

当存在热点数据的时候,命中率很高。

上述基本思路,本质:

  1. 缓存存储:HashMap 存储,get、set 都是 O(1) 时间复杂度
  2. 缓存失效
    1. 元素之间,采用「链表」形式,双向链表,方便元素调整
    2. 首尾指针,两端采用指针:尾部指针,缓存满的情况下,优先删除;头部指针,新增元素或新访问原始,插入头部

具体落地实现细节:

双向链表的几个操作:

  1. 中间删除:从其中间,删除元素
  2. 尾部删除:在尾部,删除元素
  3. 头部插入:在头部,插入元素

更多细节,参考:LRU算法

几个典型实现:

说明:

3.附录

3.1.附录:几个 Map 的底层实现

几个:TODO

3.2.附录:LRU 基本实现思路

LRU 几种实现思路:

Tips:

4.参考资料

同类文章:

微信搜索: 公众号 ningg ,即可联系我

Top