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()
    }
}