LRU缓存策略的实现
LRU算法
LRU 是 Least Recently Used 的缩写，即最近最少使用，是系统中常用的一种页面置换算法，其算法思想就是：如果一个页面最近最少使用，那么在将来它被使用的概率就很低。在 App 中，也时常将 LRU 引用为缓存的一种淘汰策略，接下来我们将使用 Swift 来实现一个基于 LRU 的缓存机制。
leetcode题目
运用所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。- 要求：get 和 put 操作都要在 O(1)的时间复杂度内完成。
来源：力扣（LeetCode）
分析需求
- 要满足 O(1) 时间复杂度，能满足的数据结构就是哈希表。
- 最久最未使用，那么数据就应该是有顺序的，数据结构中能满足的是数组和链表。
- 数组在分配内存时是连续的，在 Swift 中，扩展一个已分配空间的数组，需要重新分配更大的空间，然后将内容复制到新空间中，这种开销比较大。
- 链表的存储是分散的，单向链表要在某个位置上插入或删除一个节点的时间复杂度为 O(n)，因为需要先遍历到该位置，而双向链表则不需要遍历，比较灵活。
综上，这个缓存应该是哈希表 + 双向链表的数据结构。
代码实现
缓存的主体是哈希表，双向链表是作为一个顺序的维护。
那么我们可以把链表的节点存储到哈希表中，节点中保存 key和 value ，再通过节点的前趋和后继指针维持双向链表结构。
链表的节点
由于 Swift 的 struct 不允许自身的嵌套，即以下的写法是错误的：
struct Node {
var prev:Node
}因此选用 class 来定义链表的节点：
//链表节点
class Node {
var key,value :Int
//前趋节点、后继节点
var prev, next : Node?
init(_ key:Int,_ value:Int) {
self.key = key
self.value = value
}
deinit {
print("Node deinit :",key,"-",value)
}
}双向链表的实现
根据单一职责原则，我们将链表的实现和操作单独封装在 DuLinkList 类中，为方便调试，增加 printList() 函数来打印观察。
//双向链表实现
class DuLinkList {
//首节点、尾节点
private var header,tail : Node
init() {
header = Node.init(0, 0)
tail = Node.init(0, 0)
header.next = tail
tail.prev = header
}
///添加到链表首节点
func addToFirst(_ node:Node){
node.next = header.next
header.next?.prev = node
node.prev = header
header.next = node
}
///删除指定节点
func removeNode(_ node:Node){
//首尾节点不删除
if node.prev == nil || node.next == nil {
return
}
node.prev?.next = node.next
node.next?.prev = node.prev
node.prev = nil
node.next = nil
}
///删除最后一个节点
func removeLast() -> Node {
let note = tail.prev!
removeNode(note)
return note
}
///打印链表
func printList(){
var next = header.next
while let node = next, node.next != nil {
print("list note : ",node.key,"-",node.value)
next = node.next
}
}
///销毁链表
private func destroyList(){
var node:Node? = header
repeat{
let next = node?.next
node?.prev = nil
node?.next = nil
node = next
}while( node != nil)
}
deinit {
print("DuLinkList deinit")
destroyList()
}
}值的注意的是：双向链表的节点之间是相互引用的，构成了循环引用，会导致链表无法释放，因此增加 destroyList() 函数来销毁链表，并在 DuLinkList 类中的 deinit函数中调用。
LRUCache 的实现
/// 通过构建哈希表和双向链表来实现LRU算法
/// 其中，哈希表的 value 是 链表的的节点
class LRUCache {
//存储容量
var capacity = 5
//哈希表
private var cacheTable = Dictionary<Int,Node>()
//双向链表
private let linkList = DuLinkList()
init(_ capacity:Int) {
self.capacity = capacity
}
/// 将 value 存入哈希表中
/// 如果表中未存在，则生成节点，并存入表中，并将节点移到链表的首节点
/// 如果表中已存在，则将更新 value ，并将节点移到链表的首节点
/// 如果超出存储容量，则删除链表末尾的节点，再存入，并将节点移到链表的首节点
func put(_ key:Int,_ value:Int){
if let node = cacheTable[key] {
node.value = value
cacheTable[key] = node
//删除node节点，重新添加到链表首节点
linkList.removeNode(node)
linkList.addToFirst(node)
}else{
//创建节点
let note = Node.init(key, value)
if cacheTable.count >= capacity {
//超出容量,则删除最后一个节点、清除哈希表的 value
let temp = linkList.removeLast()
cacheTable[temp.key] = nil
}
cacheTable[key] = note
linkList.addToFirst(note)
}
}
/// 从哈希表中取出 value
/// 如果哈希表中存在value，则将对应的节点放到链表首节点,反之则返回 -1
func get(_ key:Int) -> Int? {
guard let node = cacheTable[key] else {
return -1
}
//删除node节点，重新添加到链表首节点
linkList.removeNode(node)
linkList.addToFirst(node)
return node.value
}
func printTable() {
print("cache : ",cacheTable)
linkList.printList()
print("---------------------")
}
deinit {
print("LRUCache deinit")
}
}
测试
let cache = LRUCache.init(3)
cache.put(1, 1)
cache.printTable()
cache.put(2, 2)
cache.printTable()
cache.put(3, 3)
cache.printTable()
cache.put(4, 4)
cache.printTable()
cache.put(5, 5)
cache.printTable()
print("cache get :",cache.get(3))
cache.printTable()
cache.put(4, 9)
cache.printTable()测试结果：
cache : [1: SwiftLang.Node]
list note : 1 - 1
---------------------
cache : [2: SwiftLang.Node, 1: SwiftLang.Node]
list note : 2 - 2
list note : 1 - 1
---------------------
cache : [2: SwiftLang.Node, 1: SwiftLang.Node, 3: SwiftLang.Node]
list note : 3 - 3
list note : 2 - 2
list note : 1 - 1
---------------------
Node deinit : 1 - 1
cache : [2: SwiftLang.Node, 4: SwiftLang.Node, 3: SwiftLang.Node]
list note : 4 - 4
list note : 3 - 3
list note : 2 - 2
---------------------
Node deinit : 2 - 2
cache : [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note : 5 - 5
list note : 4 - 4
list note : 3 - 3
---------------------
cache get : Optional(3)
cache : [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note : 3 - 3
list note : 5 - 5
list note : 4 - 4
---------------------
cache : [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note : 4 - 9
list note : 3 - 3
list note : 5 - 5
---------------------
LRUCache deinit
DuLinkList deinit
Node deinit : 4 - 9
Node deinit : 3 - 3
Node deinit : 5 - 5
Node deinit : 0 - 0
Node deinit : 0 - 0
