对于web开发而言缓存必不可少也是提高性能最常用的方式。无论是浏览器缓存(如果是chrome浏览器可以通过chrome:://cache查看)还是服务端的缓存(通过memcached或者redis等内存数据库)。缓存不仅可以加速用户的访问同时也可以降低服务器的负载和压力。那么了解常见的缓存淘汰算法的策略和原理就显得特别重要。像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单而且对于实际问题也很实用良好的运行时性能命中率较高。下面谈谈如何实现LRU缓存
常见的缓存算法
- LRU (Least recently used) 最近最少使用如果数据最近被访问过那么将来被访问的几率也更高。
- LFU (Least frequently used) 最不经常使用如果一个数据在最近一段时间内使用次数很少那么在将来一段时间内被使用的可能性也很小。
- 除此之外还有FIFO、随机算法等。
实现思路
LRU算法实现并不难但是要高效地实现却是有难度的要想高效实现其中的插入、删除、查找第一想法就是红黑树但是红黑树也是一种折中的办法。插入、删除效率最高当属链表查找效率当属hash。所以完全有理由想到将双向链表hashtable的方案利用空间换时间实现LRU算法。具体来说其主要包括set和get两个操作。
其基本数据结构就是一个链表
- 新数据插入时是插入到链表头部
- 每当缓存命中即缓存数据被访问就将这个数据所在的节点移到链表头部
- 当链表满的时候从链表尾部开始丢弃数据节点。
LRU Cache无非set/get两种操作
- 1、set(key,value)1如果key在hashmap中存在则先重置对应的value值一个key只能对应一个节点/value然后将该节点移动到链表的头部。2如果key在hashmap不存在则新建一个节点并将节点放到链表的头部。当Cache存满的时候将链表最后一个节点删除即可。
- 2、get(key)如果key在hashmap中存在则把对应的节点放到链表头部并返回对应的value值如果不存在则返回-1。
注其基本结构就是一个链表但是考虑到仅使用链表会存在查找效率低下的问题所以引入hashmap重新的对key-value冗余了一份。这样就兼顾了动态与静态的操作。
废话少说首先看代码
class LRUCache {private://LRU数据结构struct Node {int key;int value;Node(int k, int v) :key(k), value(v) {}};public:LRUCache(int c) :capacity(c) {}int get(int key) {if (cacheMap.find(key) cacheMap.end())return -1; //这里产生缺页中断根据页表将页面调入内存然后set(key, value)//将key移到第一个并更新cacheMap cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);cacheMap[key] cacheList.begin();return cacheMap[key]->value;}void set(int key, int value) {if (cacheMap.find(key) cacheMap.end()){//如果已经满了那么就将最后一个淘汰掉然后将该其加到第一个位置if (cacheList.size() capacity){cacheMap.erase(cacheList.back().key);cacheList.pop_back();}cacheList.push_front(Node(key, value));cacheMap[key] cacheList.begin();//确实一个key对应一个双向链表}else{//更新节点的值并将其加到第一个位置cacheMap[key]->value value;cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);cacheMap[key] cacheList.begin();}}private://最大可以容纳的节点数(key-value)对。一个key只能对应一个节点。int capacity;//自始至终都只有这么一个链表list cacheList;//cacheMap相当于以另外一种形式来存储key-value。是的查询效率变为O(1)。unordered_map 对于新手来说有以下几点需要注意 1一个key只会有一个对应的value会被保存下来不会有同一个key的多个节点被保留下来。 2链表始终只有一个而且代码中的容量capbility就是指链表的长度也就是key的个数。 3链表是真实存在的只不过每个key-value对还会以hashmap的形式存储。正如前面所述的那样兼顾了动态的插入删除操作和静态的查找操作。