1、LRU是什么宣虾？
LRU（Least recently used畜份，最近最少使用）。它是按照一個非常著名的計算機操作系統(tǒng)基礎(chǔ)理論得來的：最近使用的頁面數(shù)據(jù)會在未來一段時期內(nèi)仍然被使用忽刽，已經(jīng)很久沒有使用的頁面很有可能在未來較長的一段時間內(nèi)仍然不會被使用天揖。基于這個思想跪帝，會存在一種緩存淘汰機制今膊，每次從內(nèi)存中找到最久未使用的數(shù)據(jù)然后置換出來，從而存入新的數(shù)據(jù)伞剑！它的主要衡量指標(biāo)是使用的時間斑唬，附加指標(biāo)是使用的次數(shù)。
2黎泣、LRU的實現(xiàn)
2.1恕刘、利用雙鏈表實現(xiàn)
雙鏈表有一個特點就是鏈表方向是雙向的。每個數(shù)據(jù)元素節(jié)點有2個指針（pre前一節(jié)點/next后一節(jié)點）抒倚，從雙向鏈表的任意一點開始褐着，都可以很方便的訪問前節(jié)點和后節(jié)點。實現(xiàn)主要涉及添加托呕、訪問含蓉、修改、刪除操作项郊。
添加:新元素馅扣，直接放在表頭，其他元素順序往下移動
訪問:除頭節(jié)點外着降，如果是其他節(jié)點差油，直接將數(shù)據(jù)移到頭部
修改:修改原值之后，除頭節(jié)點外任洞，如果是其他節(jié)點蓄喇，直接將數(shù)據(jù)移到頭部
刪除:直接刪除節(jié)點，其他節(jié)點順序前移
2.2交掏、Swift代碼實現(xiàn)
2.2.1公罕、定義基本元素節(jié)點
class Node: NSObject {
// 上一個節(jié)點
var pre: Node?
// 下一個節(jié)點
var next: Node?
var key: AnyHashable
var value: Any
init(value: Any, key: AnyHashable) {
self.value = value
self.key = key
super.init()
}
override var description: String {
return "\(key):\(value)"
}
}
2.2.2、定義鏈表以及鏈表的基本操作
定義鏈表
class LinkMap: NSObject {
var headNode: Node?
var tailNode: Node?
var dict = [AnyHashable: Node]()
var totalCount: UInt64 = 0
}
鏈表基本操作--插入新元素
/// 插入新元素
///
/// - Parameter node: 元素節(jié)點
func insert(_ node: Node) {
totalCount += 1
dict[node.key] = node
if let head = headNode {
node.next = head
head.pre = node
// 重新賦值頭節(jié)點
headNode = node
} else {
headNode = node
tailNode = node
}
}
鏈表基本操作--刪除元素,我們需要做的是把該節(jié)點的前一節(jié)點的next指向當(dāng)前節(jié)點下一個節(jié)點耀销，再把當(dāng)前節(jié)點的下一節(jié)點的pre指向當(dāng)前節(jié)點的前一個節(jié)點，這樣聽起來可能有點繞铲汪，我們來畫圖來看：
/// 刪除元素
///
/// - Parameter node: 元素節(jié)點
func removeNode(_ node: Node) {
totalCount -= 1
dict.removeValue(forKey: node.key)
if let _ = node.pre {
node.pre?.next = node.next
}
if let _ = node.next {
node.next?.pre = node.pre
}
if headNode == node {
headNode = node.next
}
if tailNode == node {
tailNode = node.pre
}
}
假設(shè)現(xiàn)在要刪除3這個元素節(jié)點熊尉，我們第一步要做的就是把3的pre節(jié)點4的next指針指向3的下一個節(jié)點2，再把3的下一個節(jié)點2的pre指針指向3的上一個節(jié)點4掌腰，這樣3就消失了狰住，從4和2之間斷開了，4和2再也不需要3來進行連接齿梁，從而實現(xiàn)刪除的效果催植。
鏈表基本操作--把當(dāng)前節(jié)點移動到首部肮蛹，類似于刪除效果，先把當(dāng)前節(jié)點刪除创南，再設(shè)置當(dāng)前節(jié)點的next為頭結(jié)點伦忠，當(dāng)前節(jié)點的pre設(shè)置為nil, 頭結(jié)點的pre設(shè)置為當(dāng)前節(jié)點。最后將頭結(jié)點設(shè)置為當(dāng)前節(jié)點稿辙。
/// 把當(dāng)前節(jié)點移動到首部
///
/// - Parameter node: 元素節(jié)點
func moveNodeToHead(_ node: Node) {
if headNode == node {
return
}
// 刪除當(dāng)前節(jié)點
if tailNode == node {
tailNode = node.pre
tailNode?.next = nil
} else {
node.next?.pre = node.pre
node.pre?.next = node.next
}
// 把當(dāng)前節(jié)點移動到頭部
node.next = headNode
node.pre = nil
headNode?.pre = node
// 重新賦值頭節(jié)點
headNode = node
}
鏈表基本操作--刪除尾節(jié)點
/// 刪除尾節(jié)點
func removeTailNode() -> Node? {
totalCount -= 1
if let tail = tailNode {
let key = tail.key
dict.removeValue(forKey: key)
}
if headNode == tailNode {
return nil
} else {
tailNode = tailNode?.pre
tailNode?.next = nil
return tailNode
}
}
2.2.3昆码、操作鏈表
初始化cache，定義鏈表最大容量
init(limitCount: UInt64 = 100) {
self.limitCount = limitCount
super.init()
}
添加元素--先判斷鏈表中是否有該元素邻储，有個話赋咽，則移動到頭部，否則插入新元素吨娜。如果鏈表個數(shù)超過限制個數(shù)脓匿，刪除尾節(jié)點元素
func setobject(_ value: Any, forKey key: AnyHashable) {
lock.lock()
if let node = lru.dict[key] {
// 存在節(jié)點，則把節(jié)點移到頭部
lru.moveNodeToHead(node)
} else {
// 不存在節(jié)點宦赠，則插入新的節(jié)點
let node = Node(value: value, key: key)
lru.insert(node)
}
if lru.totalCount > limitCount {
// 數(shù)量超過限制陪毡，則刪除尾節(jié)點
let _ = lru.removeTailNode()
}
lock.unlock()
}
讀取元素--若存在元素，讀取完袱瓮，則移動到頭部
func objc(forKey key: AnyHashable) -> Any? {
lock.lock()
var node: Node?
node = lru.dict[key]
if let node = node {
lru.moveNodeToHead(node)
}
lock.unlock()
return node?.value
}
2.3缤骨、示例
let cache = Cache(limitCount: 5)
cache.setobject("a", forKey: "1")
cache.setobject("b", forKey: "2")
cache.setobject("c", forKey: "3")
cache.setobject("d", forKey: "4")
cache.setobject("e", forKey: "5")
print("原鏈表:\(cache.description)") // 5:e 4:d 3:c 2:b 1:a
let value = cache.objc(forKey: "3") ?? "zzzz"
print("value = \(value)")
print("取值之后鏈表:\(cache.description)") // 3:c 5:e 4:d 2:b 1:a
cache.setobject("f", forKey: "6")
print("新增元素之后鏈表:\(cache.description)") // 6:f 3:c 5:e 4:d 2:b
cache.removeObjc(forKey: "4")
print("刪除元素之后鏈表:\(cache.description)") // 6:f 3:c 5:e 2:b
看打印結(jié)果發(fā)現(xiàn)，無論添加和獲取元素之后整個鏈表都會將最近訪問的元素移動到頂點尺借，這樣保證了我們每次取到的最熱點的數(shù)據(jù)绊起，與我們所預(yù)想的一致。這個就是LRU重要思想燎斩。
總結(jié)
該文講述了LRU的算法基本實現(xiàn)虱歪，理解LRU算法思路，也有助于理解雙向鏈表栅表。在實際開發(fā)中也可以運用到合適的業(yè)務(wù)場景中來笋鄙。有空閑時間的同學(xué)，也可以閱讀YYMemoryCache源碼怪瓶，該文中的Demo也上傳到了GitHub中萧落，有需要的同學(xué)也可以下載。
