Lrucache

Q：一天共事问，我放在 redis 中的 key，为什么有时候过一段时间数据就没有了，我并没有设置过期工夫呀？？ A：你的 redis 淘汰策略是什么样的，这个 key 可能是被 redis 本身的淘汰策略干掉了 一看 redis 的 config 文件 redis.conf 果然，你配置的是 maxmemory_policy allkey-lfu ，这个是 Redis 中的淘汰策略，是会从 redis 数据集中筛选应用频率最低的数据进行淘汰的 Q：不明觉厉，摸摸头 A：我给你简略说一下对于 redis 的淘汰策略吧 首先，redis 删除数据的策略目前来看有三种 定时删除见名知意，定时，天然就像咱们定起床闹钟一样，此处是定一个删除 key 的闹钟，当咱们对一个 key 设置过期工夫的时候，会同时开启一个定时器，当工夫到到的时候，就会删除这个 key 这种形式，须要咱们额定开一个定时器，会耗费 CPU 资源 惰性删除惰性，一看就晓得这种删除形式是被动的，若一个 key 过期了，redis 不会被动去删除他，而是当这个 key 再次被拜访的时候，redis 看他有没有生效，若生效，则删除他 这种形式能够看出，如果一些过期的 key ，再没有被再次拜访之前，就会始终存在内存中，十分节约内存资源 被动删除顾名思义，这种形式是 redis 中会去设置各种策略，去依照不同的策略去删除一些不符合要求的数据，简略的，咱们来看看 Redis 的淘汰策略，把握主动权 Redis 的淘汰策略 能够看出 redis 的淘汰策略大体上有 5 种形式 LRU<!----> LFU<!----> RANDOM会从数据集中随机抉择数据进行删除，依照配置的策略不同 allkeys-random 则是将在所有数据集中进行随机 ， volatile-random 是在曾经设置了过期工夫的数据中去随机淘汰 ...

缓存算法缓存算法是编程中的根本算法，用于解决缓存的更新和替换问题，通过正当地抉择缓存中数据的存储地位，能够进步零碎的访问速度和性能。本文介绍几个通用的缓存算法，这些算法实用于多种利用场景的缓存策略，其指标是在限定的缓存空间内，最大化缓存命中率，同时最小化缓存淘汰率。 随机替换 (Random Replacement，RR)：随机抉择一个数据项淘汰。先进先出（First In First Out, FIFO）：依据数据项进入缓存的工夫先后，淘汰最早进入缓存的数据项。最近起码应用（Least Recently Used, LRU）：依据数据项最近被拜访的工夫，淘汰最久未被应用的数据项。起码应用（Least Frequently Used, LFU）：依据数据项被拜访的频率，淘汰拜访次数起码的数据项。掂量指标掂量一个缓存算法的品质，通常看以下指标： 命中率（Hit Rate）：即缓存中已缓存的数据被拜访的次数与所有拜访次数的比值，反映了缓存算法对于热点数据的缓存成果。缓存空间利用率（Cache Space Utilization）：即缓存中曾经占用的空间与总空间的比值，反映了缓存算法对于缓存空间的利用效率。替换次数（Replacement Count）：即缓存中数据被替换的次数，反映了缓存算法对于缓存数据的爱护能力。缓存访问速度（Cache Access Speed）：即缓存中数据被拜访的速度，反映了缓存算法对于访问速度的晋升成果。不过值得注意的是，不同利用场景和需要会对缓存算法的指标有不同的要求，比方某些场景可能更重视命中率和访问速度，而另一些场景则可能更重视缓存空间利用率和替换次数。因而，在抉择缓存算法时，须要依据理论状况进行衡量和抉择。 随机替换 (RR)随机替换 (Random Replacement，RR) 算法的核心思想是随机抉择要被替换的缓存块，从而保障所有缓存块被替换的概率相等。在缓存空间无限的状况下，当须要替换缓存中的某个数据块时，RR 算法会从以后缓存中随机抉择一个数据块进行替换。 长处： 实现简略，容易了解和实现。在缓存大小较大时体现良好，可能缩小缓存替换的次数，进步缓存命中率。毛病： 算法性能不稳固，在缓存大小较小时，体现较差，因为随机替换可能导致频繁的缓存替换，升高了缓存的命中率。无奈适应不同数据拜访模式的需要，不能利用数据局部性进行缓存优化。实用场景： 随机替换算法实用于数据拜访模式比拟随机的场景，缓存大小比拟大，缓存替换代价比拟高的场景。例如，在内存比拟短缺的状况下，应用随机替换算法能够进步缓存命中率，缩小缓存替换的次数，进步零碎性能。然而，在缓存容量较小、数据拜访模式具备显著局部性的场景下，随机替换算法的体现会较差。 上面是一个Java 例子： import java.util.HashMap;import java.util.LinkedList;import java.util.Queue;import java.util.Random;public class CacheRR<K, V> { private int capacity; // 缓存容量 private HashMap<K, V> map; // 用于存储缓存数据 private Queue<K> queue; // 用于存储缓存数据的key，以便进行随机替换 public CacheRR(int capacity) { this.capacity = capacity; map = new HashMap<>(); queue = new LinkedList<>(); } /** * 从缓存中获取数据 * @param key 缓存数据的key * @return 缓存数据的value，若不存在则返回null */ public synchronized V get(K key) { return map.get(key); } /** * 往缓存中增加数据 * @param key 缓存数据的key * @param value 缓存数据的value */ public synchronized void put(K key, V value) { // 如果缓存已满，则进行随机替换 if (map.size() == capacity) { K randomKey = queue.poll(); map.remove(randomKey); } // 增加新数据 map.put(key, value); queue.offer(key); } /** * 获取缓存的大小 * @return 缓存的大小 */ public synchronized int size() { return map.size(); }}这段代码实现了一个基于随机替换（RR）算法的缓存，它应用了HashMap来存储缓存数据，并应用Queue来存储缓存数据的key。当缓存达到容量下限时，会从队列中随机抉择一个key进行替换，以保障替换的公平性。先进先出（FIFO）先进先出（First-In-First-Out, FIFO）缓存算法是一种比较简单的缓存淘汰算法，它将最早进入缓存的数据先进来，也就是先进入缓存的数据先被淘汰。 ...

题目 解题的关键在于LRU构造体和双向链表构造体的设计以及双向链表的四个性能函数的拆分这使得题解优雅而简洁 （想起来上学期苦楚的课程） type LRUCache struct { size int capacity int cache map[int]*DLinkedNode head, tail *DLinkedNode}type DLinkedNode struct { key, value int prev, next *DLinkedNode}func initDLinkedNode(key, value int) *DLinkedNode { return &DLinkedNode{ key: key, value: value, }}func Constructor(capacity int) LRUCache { l := LRUCache{ cache: map[int]*DLinkedNode{}, head: initDLinkedNode(0, 0), tail: initDLinkedNode(0, 0), capacity: capacity, } l.head.next = l.tail l.tail.prev = l.head return l}//int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。//对于 get 操作，首先判断 key 是否存在：//如果 key 不存在，则返回 -1−1；//如果 key 存在，则 key 对应的节点是最近被应用的节点。通过哈希表定位到该节点在双向链表中的地位，并将其挪动到双向链表的头部，最初返回该节点的值。func (this *LRUCache) Get(key int) int { if _, ok := this.cache[key]; !ok { return -1 } node := this.cache[key] this.moveToHead(node) return node.value}//void put(int key, int value)如果关键字key 曾经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未应用的关键字。//对于 put 操作，首先判断 key 是否存在：//如果 key 不存在，应用 key 和 value 创立一个新的节点，在双向链表的头部增加该节点，并将 key 和该节点增加进哈希表中。而后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；//如果 key 存在，则与 get 操作相似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。func (this *LRUCache) Put(key int, value int) { if _, ok := this.cache[key]; !ok { node := initDLinkedNode(key, value) this.cache[key] = node this.addToHead(node) this.size++ if this.size > this.capacity { removed := this.removeTail() delete(this.cache, removed.key) this.size-- } } else { node := this.cache[key] node.value = value this.moveToHead(node) }}func (this *LRUCache) addToHead(node *DLinkedNode) { node.prev = this.head node.next = this.head.next this.head.next.prev = node this.head.next = node}func (this *LRUCache) removeNode(node *DLinkedNode) { node.prev.next = node.next node.next.prev = node.prev}func (this *LRUCache) moveToHead(node *DLinkedNode) { this.removeNode(node) this.addToHead(node)}func (this *LRUCache) removeTail() *DLinkedNode { node := this.tail.prev this.removeNode(node) return node}