LRU

LRU(least recently used) 最近最少使用的 ，核心思想：如果数据最近被访问，将来被访问的概率也高

数据结构

用链表结果实现

网上的图.png

步骤：
1.新插入数据放在表头
2.最近访问数据移动到表头
3.当链表满了，就将尾部数据丢弃

命中概率

根据实际软件情况使用

代码实现

简单，项目工程，这里不像c那样，查找一个节点，真得一个一个遍历，这里有一个字典来存节点，直接找
LinkedImplementsViewController.swift有实现

class LURCache {
   class CacheNode {
       var prev: CacheNode?
       var next: CacheNode?
       var data: Any?
       var key     = ""
       deinit{
           print("\(self.key) is die")
       }
   }
   private var cacheSize                           = 0
   lazy private  var nodes :[String: CacheNode]     = [:]
   private var currentSize                         = 0
   private var firstNode: CacheNode?
   private var lastNode: CacheNode?
   
   init(cacheSize :Int){
       self.cacheSize = cacheSize
   }
   func get(key : String) -> Any? {
       let tmpNode = nodes[key]
       move2Head(tmpNode)
       return tmpNode?.data
   }
   func put(key: String , anyO: Any){
       var tmpNode = nodes[key]
       if nil == tmpNode {
           if currentSize >= cacheSize {
               removeLast()
           }
           currentSize++
           tmpNode = CacheNode()
       }
       tmpNode!.key = key
       tmpNode!.data = anyO
       move2Head(tmpNode!)
       nodes[key] = tmpNode
   }
   func remove(key : String) -> CacheNode?{
       let tmpNode = nodes[key]
       if let node = tmpNode {
           if node.prev != nil {
               node.prev?.next = node.next
           }
           if node.next != nil {
               node.next?.prev = node.prev
           }
           if lastNode === tmpNode{
               lastNode = tmpNode?.prev
           }
           
           if firstNode === tmpNode {
               firstNode = tmpNode?.next
           }
           nodes[key] = nil
           currentSize--
       }
       return tmpNode
   }
   //清空缓存
    func clear(){
       firstNode = nil
       lastNode = nil
       nodes.removeAll()
   }
   private func removeLast(){
       if let lastn = lastNode {
           nodes[lastn.key] = nil//从缓存中删除
           currentSize--
           if let lastPre = lastn.prev {
                   lastPre.next = nil
               }else{
                   firstNode = nil
               }
               lastNode = lastNode?.prev
           }
   }
   
   
   private func move2Head(node: CacheNode?){
       if let n = node {
           if node === firstNode{
               return
           }
           
           if n.prev != nil {
               n.prev?.next = n.next
           }
           
           if n.next != nil{
               n.next?.prev = n.prev
           }
           
           if lastNode === node{
               lastNode  = n.prev
           }
           
           if firstNode != nil {
               n.next = firstNode
               firstNode?.prev = n
           }
           
           firstNode = node
           
           n.prev = nil
           
           if lastNode == nil{
               lastNode  = firstNode
           }

       }
   }

}

LRU-K

是在LRU的基础上为了提高命中率。

网上的图.png

1. 数据第一次被访问，加入到访问历史列表；
2. 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
3. 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
4. 缓存数据队列中被再次访问后，重新排序；
5. 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。
   LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。