培训机构网站建设要求,dedecms 金融类网站模板,域名一级和二级的区别,北京医疗网站建设目录 1.概述2.代码实现2.1.FIFO2.2.LRU2.3.LFU2.4.Clock2.5.Random 3.应用 1.概述
缓存淘汰策略是指在缓存容量有限的情况下#xff0c;当缓存空间不足时决定哪些缓存项应当被移除的策略。缓存淘汰策略的目标是尽可能地保持缓存命中率高#xff0c;同时合理地利用有限的缓存… 目录 1.概述2.代码实现2.1.FIFO2.2.LRU2.3.LFU2.4.Clock2.5.Random 3.应用 1.概述
缓存淘汰策略是指在缓存容量有限的情况下当缓存空间不足时决定哪些缓存项应当被移除的策略。缓存淘汰策略的目标是尽可能地保持缓存命中率高同时合理地利用有限的缓存空间。 需要注意的是下面的代码实现只是对缓存淘汰算法的基本实现在实际情况中可以需要考虑更多的因素 2.代码实现
2.1.FIFO
1FIFO (First-In-First-Out) 是一种基本的内存淘汰策略。其思路是按照元素的进入顺序来选择要淘汰的元素。具体来说当有新的元素要加入到固定容量的缓存中时如果缓存已满就需要选择一个元素进行淘汰以腾出空间存储新的元素。在 FIFO 策略中选择被缓存时间最长的元素进行淘汰。
2FIFO 策略维护一个队列在每次新元素加入缓存时将新元素添加到队列的末尾。当需要淘汰元素时选择队列的头部元素作为淘汰对象即最早进入缓存的元素。通过这种方式始终保持最早进入缓存的元素在队列头部最新进入缓存的元素在队列末尾。
3使用 FIFO 策略的好处是它的实现简单且执行效率高。然而它没有考虑元素的访问频率或重要性等因素只根据进入缓存的顺序来进行淘汰可能会导致缓存中的数据不够优化。因此在某些应用场景下FIFO 策略可能不是最优选择需要根据实际需求选择更复杂的内存淘汰策略。其具体代码实现如下
class FIFOCacheK, V {private int capacity;private DequeK queue;private MapK, V cache;//进行初始化操作public FIFOCache(int capacity) {this.capacity capacity;this.queue new ArrayDeque(capacity);this.cache new HashMap(capacity);}//接收一个键 key 并返回相应的值如果键不存在则返回 nullpublic V get(K key) {return cache.getOrDefault(key, null);}//接收一个键 key 和一个值 value并将它们存储在缓存中public void put(K key, V value) {if (!cache.containsKey(key)) {//如果缓存已满将使用队列的 poll 方法移除最早加入的键if (queue.size() capacity) {K oldestKey queue.poll();cache.remove(oldestKey);}//然后将新的键加入队列的尾部queue.offer(key);}//将新的键值对加入缓存cache.put(key, value);}public V remove(K key) {//从队列中移除指定键queue.remove(key); // 从缓存中移除指定键并返回对应的值return cache.remove(key); }public void clear() {//清空队列queue.clear(); //清空缓存cache.clear(); }public int size() {return cache.size();}
}2.2.LRU
参考 146.LRU 缓存这篇文章。
2.3.LFU
参考 460.LFU 缓存这篇文章。
2.4.Clock
1Clock 缓存淘汰算法是一种基于近似“最近未使用” (Not Recently Used) 策略的淘汰算法。该算法通过维护一个环形指针数组 (Clock)来判断缓存项是否被使用从而进行淘汰决策。Clock 缓存淘汰算法的思路如下
对于每个缓存项维护一个额外的访问位来标记缓存项是否被访问过。初始状态下将所有缓存项的访问位都设置为 0。创建一个环形指针数组数组中的每个槽位对应一个缓存项并按照某种顺序排列。当需要淘汰一个缓存项时根据指针指向的槽位判断 如果该槽位的访问位为 0表示该缓存项最近未被使用可以选择淘汰。如果该槽位的访问位为 1表示该缓存项最近被使用过将访问位置为 0并将指针向后移动一位。 重复第 4 步直到找到一个访问位为 0 的槽位将该缓存项置换出来让出空间给新的缓存项。如果需要访问某个缓存项时将其对应的访问位置为 1表示该缓存项已被使用。
2Clock 缓存淘汰算法相对于经典的最近未使用 (LRU) 算法具有更低的时间和空间复杂度。它通过近似地追踪缓存项的访问状态来进行淘汰决策适用于中小规模的缓存系统。
3然而需要注意的是Clock 算法可能出现缓存项的“反复使用”情况即缓存项被不断地替换出去又被重新引入这可能会影响缓存的命中率。因此在实际应用中需要根据具体场景和需求综合考虑各个因素选择合适的缓存淘汰策略。其具体代码实现如下
class ClockCacheK, V {//循环链表节点static class CircleListNodeK, V {K key;V value;boolean accessFlag;CircleListNodeK, V pre;CircleListNodeK, V next;public CircleListNode() {}public CircleListNode(K key, V value) {this.key key;this.value value;}}private int capacity;//头节点private CircleListNodeK, V dummyHead;private MapK, CircleListNodeK, V cache;public ClockCache(int capacity) {this.capacity capacity;this.dummyHead new CircleListNode();this.dummyHead.next this.dummyHead;this.dummyHead.pre this.dummyHead;this.cache new HashMap();}public V get(K key) {if (cache.containsKey(key)) {CircleListNodeK, V node cache.get(key);//将访问位设置为 truenode.accessFlag true;return node.value;} else {return null;}}public void put(K key, V value) {if (cache.containsKey(key)) {CircleListNodeK, V node cache.get(key);//将访问位设置为 truenode.accessFlag true;node.value value;} else {if (cache.size() capacity) {//从最老的元素开始此处直接从 head.next 开始后续可以考虑优化记录这个 keyCircleListNodeK, V node this.dummyHead;boolean removeFlag false;while (node.next ! this.dummyHead) {//下一个元素node node.next;if (!node.accessFlag) {//未访问直接淘汰removeNode(node);System.out.println(node.key);removeFlag true;break;} else {//设置当前 accessFlag 为 false继续遍历下一个node.accessFlag false;}}if (!removeFlag) {//如果循环一遍都没找到直接取第一个元素即可CircleListNodeK, V firstNode this.dummyHead.next;System.out.println(firstNode.key);removeNode(firstNode);}}CircleListNodeK, V newNode new CircleListNode(key, value);newNode.accessFlag true;CircleListNodeK, V tail dummyHead.pre;tail.next newNode;newNode.pre tail;newNode.next dummyHead;dummyHead.pre newNode;cache.put(key, newNode);}}public void remove(K key) {CircleListNodeK, V node cache.get(key);if (node ! null) {cache.remove(key);removeNode(node);}}public void clear() {cache.clear();}public int size() {return cache.size();}private void removeNode(CircleListNodeK, V node) {CircleListNodeK, V pre node.pre;CircleListNodeK, V next node.next;pre.next next;next.pre pre;cache.remove(node.key);}
}2.5.Random
1Random随机内存淘汰算法的思想是基于随机选择的策略来进行缓存淘汰。该算法不依赖于缓存项的访问频率或时间等信息而是通过随机选择一个缓存项进行淘汰没有明确的优先级或规则。Random 内存淘汰算法的思想如下
当缓存空间不足时需要淘汰一个缓存项。使用随机数生成器如 Random 类来生成一个随机索引范围为缓存的容量。根据生成的随机索引随机选择一个缓存项进行淘汰。被选择的缓存项被移除让出空间给新的缓存项。
2随机选择的特点使得每个缓存项被淘汰的概率相等没有明确的优先级所有缓存项都有被淘汰的可能性。这种随机性的特点适用于一些无规律或无明确访问模式的缓存使用场景。然而随机内存淘汰算法可能导致缓存命中率下降因为被频繁访问的缓存项有可能被随机选中被淘汰从而增加缓存不命中的概率。 因此在选择淘汰算法时需要根据具体应用场景和缓存使用模式来权衡各种算法的优劣并选择适合的淘汰策略以达到最优的性能。 3其具体代码实现如下
class RandomCacheK, V {private int capacity;private ListK keys;private MapK, V cache;private Random random;public RandomCache(int capacity) {this.capacity capacity;this.keys new ArrayList(capacity);this.cache new HashMap(capacity);this.random new Random();}//接收一个键 key 并返回相应的值如果键不存在则返回 nullpublic V get(K key) {return cache.getOrDefault(key, null);}public void put(K key, V value) {if (!cache.containsKey(key)) {//如果缓存已满将使用 Random 对象的 nextInt 方法随机选择一个键索引并从列表中移除键if (keys.size() capacity) {int index random.nextInt(capacity);K randomKey keys.remove(index);cache.remove(randomKey);}keys.add(key);}cache.put(key, value);}public V remove(K key) {if (cache.containsKey(key)) {//从列表中移除指定键keys.remove(key); //从缓存中移除指定键并返回对应的值return cache.remove(key);}return null;}public void clear() {keys.clear(); cache.clear(); }public int size() {return cache.size();}
}3.应用
Redis 的缓存淘汰策略如下 有关上面淘汰策略的一些具体说明如下
noevction 是 Redis 的默认配置。当缓存被写满时再有写请求进来Redis 不再提供服务直接返回错误。LRU 和 LFU 算法是常见的淘汰算法其具体细节可以参考 146.LRU 缓存、460.LFU 缓存这两篇文章。random 指随机删除相关的算法实现可以参考 380. O(1) 时间插入、删除和获取随机元素这篇文章。volatile-ttl 策略针对设置了过期时间的键值对根据过期时间的先后进行删除越早过期的数据越先被淘汰即 ttl 越小的数据越优先被淘汰这里的 ttl 指 Time to Live即生存时间。
要想设置 Redis 的缓存淘汰策略可以在其配置文件 redis.conf 中进行 maxmemory-policy 具体淘汰策略 的设置例如设置淘汰策略为 volatile-lru
maxmemory-policy volatile-lru
