牛商网站建设,重庆 建网站,视屏网站的审核是怎么做的,网站如何做分站系统序、慢慢来才是最快的方法。
背景 LinkedHashMap 是继承于 HashMap 实现的哈希链表#xff0c;它同时具备双向链表和散列表的特点。事实上#xff0c;LinkedHashMap 继承了 HashMap 的主要功能#xff0c;并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。 1.缓存淘汰算法…序、慢慢来才是最快的方法。
背景 LinkedHashMap 是继承于 HashMap 实现的哈希链表它同时具备双向链表和散列表的特点。事实上LinkedHashMap 继承了 HashMap 的主要功能并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。 1.缓存淘汰算法
1.1什么是缓存淘汰算法
缓存是提高数据读取性能的通用技术在硬件和软件设计中被广泛使用例如CPU缓存Glide缓存内存缓存数据库缓存。由于缓存空间不可能无限大当缓存容量占满时就需要利用某种策略将部分数据换出缓存这就是缓存的淘汰问题/替换策略。
常见的缓存淘汰策略有 1、随机策略 使用一个随机数生成器随机地选择要被淘汰的数据块 2、FIFO 先进先出策略 记录各个数据块的访问时间最早访问的数据最先被淘汰 3、LRU Least Recently Used最近最少策略 记录各个数据块的访问 “时间戳” 最近最久未使用的数据最先被淘汰。与前 2 种策略相比LRU 策略平均缓存命中率更高这是因为 LRU 策略利用了 “局部性原理”最近被访问过的数据将来被访问的几率较大最近很久未访问的数据将来访问的几率也较小 4、LFU Least Frequently Used最不经常使用策略 与 LRU 相比LFU 更加注重使用的 “频率” 。LFU 会记录每个数据块的访问次数最少访问次数的数据最先被淘汰。但是有些数据在开始时使用次数很高以后不再使用这些数据就会长时间污染缓存。可以定期将计数器右移一位形成指数衰减。
FIFO和LRU策略图形解释 1.2向外看LRU的变型
在标准的LRU算法上还有一些变型实现这是因为LRU算法本身也存在一些不足。例如当数据中热点数据较多时LRU能够保证较多的命中率。但是当有偶然的批量的非热点数据产生时就会讲热点数据寄出缓存是的缓存被污染。因此LRU也有一些变型。
LRU-K 提供两个 LRU 队列一个是访问计数队列一个是标准的 LRU 队列两个队列都按照 LRU 规则淘汰数据。当访问一个数据时数据先进入访问计数队列当数据访问次数超过 K 次后才会进入标准 LRU 队列。标准的 LRU 算法相当于 LRU-1Two Queue 相当于 LRU-2 的变型将访问计数队列替换为 FIFO 队列淘汰数据数据。当访问一个数据时数据先进入 FIFO 队列当第 2 次访问数据时才会进入标准 LRU 队列Multi Queue 在 LRU-K 的基础上增加更多队列提供多个级别的缓冲。
1.3如何实现LRU缓存淘汰算法
我们尝试找到 LRU 缓存淘汰算法的实现方案。经过总结我们可以定义一个缓存系统的基本操作 我们发现前 3 个操作都有 “查询” 操作 所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。 下面我们用递推的思路推导 LRU 缓存的实现方案主要分为 3 种方案 PS双向链表散列表这种数据结构就叫“哈希链表或链式哈希表”Java的LinkedHashMap就是基于哈希链表的数据结构。 2.LinkedHashMap哈希链表
PS需要注意LinkedHashMap 中的 “Linked” 实际上是指双向链表并不是指解决散列冲突中的分离链表法。
2.1LinkedHashMap 的特点 2.2说一下 HashMap 和 LinkedHashMap 的区别 操作 1 - 添加数据 先查询数据是否存在不存在则添加数据存在则更新数据并尝试淘汰数据操作 2 - 删除数据 先查询数据是否存在存在则删除数据操作 3 - 查询数据 如果数据不存在则返回 null 操作 4 - 淘汰数据 添加数据时如果容量已满则根据缓存淘汰策略一个数据。 方案 1 - 基于时间戳的数组 在每个数据块中记录最近访问的时间戳当数据被访问添加、更新或查询时将数据的时间戳更新到当前时间。当数组空间已满时则扫描数组淘汰时间戳最小的数据。 查找数据 需要遍历整个数组找到目标数据时间复杂度为 O(n)淘汰数据 需要遍历整个数组找到时间戳最小的数据且在移除数组元素时需要搬运数据整体时间复杂度为 O(n)。 方案 2 - 基于双向链表 不再直接维护时间戳而是利用链表的顺序隐式维护时间戳的先后顺序。当数据被访问添加、更新或查询时将数据插入到链表头部。当空间已满时直接淘汰链表的尾节点。 查询数据需要遍历整个链表找到目标数据时间复杂度为 O(n)淘汰数据直接淘汰链表尾节点时间复杂度为 O(1)。 方案 3 - 基于双向链表 散列表 使用双向链表可以将淘汰数据的时间复杂度降低为 O(1)但是查询数据的时间复杂度还是 O(n)我们可以在双向链表的基础上增加散列表将查询操作的时间复杂度降低为 O(1)。 查询数据通过散列表定位数据时间复杂度为 O(1)淘汰数据直接淘汰链表尾节点时间复杂度为 O(1)。 1、LinkedHashMap 是继承于 HashMap 实现的哈希链表它同时具备双向链表和散列表的特点。事实上LinkedHashMap 继承了 HashMap 的主要功能并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。 1.1 当 LinkedHashMap 作为散列表时主要体现出 O(1) 时间复杂度的查询效率1.2 当 LinkedHashMap 作为双向链表时主要体现出有序的特性。 2、LinkedHashMap 支持 2 种排序模式这是通过构造器参数 accessOrder 标记位控制的表示是否按照访问顺序排序默认为 false 按照插入顺序。 2.1 插入顺序默认 按照数据添加到 LinkedHashMap 的顺序排序即 FIFO 策略2.2 访问顺序 按照数据被访问包括插入、更新、查询的顺序排序即 LRU 策略。 3、在有序性的基础上LinkedHashMap 提供了维护了淘汰数据能力并开放了淘汰判断的接口 removeEldestEntry()。在每次添加数据时会回调 removeEldestEntry() 接口开发者可以重写这个接口决定是否移除最早的节点在 FIFO 策略中是最早添加的节点在 LRU 策略中是最早未访问的节点 4、与 HashMap 相同LinkedHashMap 也不考虑线程同步也会存在线程安全问题。可以使用 Collections.synchronizedMap 包装类其原理也是在所有方法上增加 synchronized 关键字。
事实上HashMap 和 LinkedHashMap 并不是平行的关系而是继承的关系LinkedHashMap 是继承于 HashMap 实现的哈希链表。
两者主要的区别在于有序性 LinkedHashMap 会维护数据的插入顺序或访问顺序而且封装了淘汰数据的能力。在迭代器遍历时HashMap 会按照数组顺序遍历桶节点从开发者的视角看是无序的。而是按照双向链表的顺序从 head 节点开始遍历从开发者的视角是可以感知到的插入顺序或访问顺序。
LinkedHashMap 继承于 HashMap在后者的基础上通过双向链表维护节点的插入顺序或访问顺序。因此我们先回顾下 HashMap 为 LinkedHashMap 预留的 Hook 点 参考
afterNodeAccess 在节点被访问时回调afterNodeInsertion 在节点被插入时回调其中有参数 evict 标记是否淘汰最早的节点。在初始化、反序列化或克隆等构造过程中evict 默认为 false表示在构造过程中不淘汰。 afterNodeRemoval 在节点被移除时回调。
Java Android 集合框架 #7 如何使用 LinkedHashMap 实现 LRU 缓存 - 掘金
