LRU是一种常见的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进行选择。
LRU原理
LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。
LRU的实现方式有很多种，一般比较常见的就是双向链表+字典（哈希表）的方式，在iOS端实现该方式的就有 YYMemoryCache
其YYMemoryCache目前提供的功能有如下：
/** 缓存名称. */
@property (nullable, copy) NSString *name;
/** 对象数 */
@property (readonly) NSUInteger totalCount;
/**
最大对象数
*/
@property NSUInteger countLimit;
/**
缓存中是否包含某个key
*/
- (BOOL)containsObjectForKey:(id)key;
/**
将缓存的对象返回
*/
- (nullable id)objectForKey:(id)key;
/**
将某对象添加进缓存
*/
- (void)setObject:(nullable id)object forKey:(id)key;
/**
移除某个对象
*/
- (void)removeObjectForKey:(id)key;
/**
清空缓存
*/
- (void)removeAllObjects;
/**
超出最大数后，删除超出部分缓存
*/
- (void)trimToCount:(NSUInteger)count;
YYMemoryCache其底层是使用双向链表+字典的方式来实现的；
_YYLinkedMapNode 为双向链表的节点
_YYLinkedMap是管理双向链表以及实现LRU算法的核心
_YYLinkedMapNode其结构如下
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
id _key;
id _value;
NSUInteger _cost;
NSTimeInterval _time;
}
@end
_YYLinkedMap其结构如下
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; // do not set object directly
NSUInteger _totalCost;
NSUInteger _totalCount;
_YYLinkedMapNode *_head; // MRU, do not change it directly
_YYLinkedMapNode *_tail; // LRU, do not change it directly
BOOL _releaseOnMainThread;
BOOL _releaseAsynchronously;
}
//在头部插入
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
//将某个节点取出重置到头部，LRU算法的核心，当有某个节点二次被使用的时候，将该节点的位置提前放到head处
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
//删除某个节点
- (void)removeNode:(_YYLinkedMapNode *)node;
//从尾部删除节点，也可以认为是淘汰某个节点
- (_YYLinkedMapNode *)removeTailNode;
//清空
- (void)removeAll;
下面是模仿YYMemoryCache用swift双链表+字典来做的实现：
class FMMemmoryCache:NSObject{
var lruMap:FMDoubleLinkWithLRU = FMDoubleLinkWithLRU<Any>()
//缓存最大数
var limitCount:Int = 5
//当前缓存数
var currentLimit:Int {
get{
return lruMap.dic.count
}
}
override init(){
}
//是否包含某个key
func containsObjectForKey(_ key:String) -> Bool{
return lruMap.dic.keys.contains(key)
}
//返回在缓存中，key所对应的具体值
func objectForKey(_ key:String) -> Any?{
return lruMap.dic[key]?.val
}
//向缓存中添加某个对象，并设置key值
func append(_ obj:Any,key:String){
if self.containsObjectForKey(key){
let node = lruMap.dic[key]!
lruMap.bringNodeToHead(node)
}else{
let node = FMDoubleLinkNode<Any>.init(key, obj)
lruMap.insertNodeAtHead(node)
}
self.trimToCount()
}
//移除缓存中的某个对象
func removeObjectForKey(_ key:String){
if lruMap.dic.keys.contains(key){
lruMap.removeNode(lruMap.dic[key]!)
}
}
//超出最大限制数量，进行删减
func trimToCount(){
while lruMap.dic.count > self.limitCount{
lruMap.removeTailNode()
}
}
}
class FMDoubleLinkNode<T>:NSObject{
var val:T?
var key:String
weak var preNode:FMDoubleLinkNode? = nil
weak var nextNode:FMDoubleLinkNode? = nil
init(_ key:String,_ val:T?) {
self.key = key
self.val = val
}
}
class FMDoubleLinkWithLRU<T>:NSObject{
var dic:[String:FMDoubleLinkNode<T>] = [String:FMDoubleLinkNode<T>]()
//这里采用虚拟的头结点
var head:FMDoubleLinkNode<T> = FMDoubleLinkNode<T>.init("", nil)
var tail:FMDoubleLinkNode<T> = FMDoubleLinkNode<T>.init("", nil)
// //当前缓存数
// var currentLimit:Int = 0
override init() {
self.head.nextNode = tail
self.tail.preNode = self.head
}
}
extension FMDoubleLinkWithLRU{
func insertNodeAtHead(_ node:FMDoubleLinkNode<T>){
node.preNode = self.head
node.nextNode = self.head.nextNode
node.nextNode?.preNode = node
self.head.nextNode = node
self.dic[node.key] = node
}
func bringNodeToHead(_ node:FMDoubleLinkNode<T>){
if self.dic.count < 2 {
return
}
node.preNode?.nextNode = node.nextNode
node.nextNode?.preNode = node.preNode
self.insertNodeAtHead(node)
}
func removeNode(_ node:FMDoubleLinkNode<T>){
if self.dic.count < 1 {
return
}
node.preNode?.nextNode = node.nextNode
node.nextNode?.preNode = node.preNode
self.dic.removeValue(forKey: node.key)
}
func removeTailNode(){
if self.dic.count < 1 {
return
}
if let key = self.tail.preNode?.key{
self.dic.removeValue(forKey: key)
self.tail.preNode = self.tail.preNode?.preNode
self.tail.preNode?.nextNode = self.tail
}
}
func removeAll(){
if self.dic.count < 1 {
return
}
self.head.nextNode = self.tail
self.tail.preNode = self.head
self.dic.removeAll()
}
}
