如何用 Swift 来实现一个 LRU 缓存呢?
计算机的缓存容量是有限的,当缓存满的时候,我们需要删除旧数据,给新的数据腾出位置。 那么问题来了,我们应该删除哪些数据呢?也就是说应该使用哪种缓存策略呢?
LRU(Least Recently Used)就是其中一种缓存淘汰策略。LRU 认为最近使用过的缓存是有用的,缓存满了应该优先删除那些没使用过的。
思路 LRU 缓存主要的操作方法是 put
和 get
,put
用于增加缓存,get
用于查找缓存。我们要保证这两个操作的时间复杂度是 O(1)。
我们知道,链表可以在 O(1) 的时间里删除、插入一个数据。哈希表可以在 O(1) 的时间里查询元素。
LRU 会同时使用这两种数据结构的组合,称之为哈希链表,其中的链表是双向的,为什么是双向链表呢?因为我们删除一个节点的时候,需要知道这这个节点的前驱节点和后继节点。
我们需要三种数据结构:
1、用于存储单个数据的 Node
2、用于存储多个数据的双向链表 DoubleNodeList
3、用于表示缓存的 LRUCache
接下来用 Swift 语言实现一个 LRU 缓存。
实现 Node 首先编写我们的数据节点类 Node。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Node { var key: Int var value: Int var pre: Node? var next: Node? var identifier: String init (_ key: Int , _ value: Int ) { self .key = key self .value = value self .identifier = UUID ().uuidString } } extension Node : Equatable { static func == (lhs: Node, rhs: Node) -> Bool { return lhs.identifier == rhs.identifier } }
DoubleList 接着编写我们的双向链表类 DoubleList。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class DoubleList { private var head: Node private var tail: Node private (set ) var size: Int init () { head = Node (0 , 0 ) tail = Node (0 , 0 ) head.next = tail tail.pre = head size = 0 } func addLast (_ node: Node) { tail.prev?.next = node node.next = tail node.pre = tail.prev tail.prev = node size += 1 } func remove (_ node: Node) { node.pre?.next = node.next node.next?.pre = node.pre size -= 1 } func removeFirst () -> Node? { if head.next == tail { return nil } let first = head.next! self .remove(first) return first } }
这个双向链表主要有三个操作:
addLast 在链表尾部添加新的节点,步骤见下图。
remove 删除某个节点,步骤见下图。
removeFirst 删除头结点
添加节点的 4 个步骤如图所示:
删除节点的 2 个步骤如图所示
LRUCache 最后实现我们的 LRU 缓存类 LRUCache。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 class LRUCache { private var hashMap: [Int : Node ] private var cache: DoubleList private var cap: Int init (_ cap: Int ) { self .hashMap = [Int : Node ]() self .cache = DoubleList () self .cap = cap } func get (key: Int) -> Int { if !hashMap.keys.contains (key) { return -1 } self .makeRecently(key) return hashMap[key]!.value } func put (key: Int, value: Int) { if hashMap.keys.contains (key) { self .deleteKey(key) self .addRecently(key, value) return } if cap == cache.size { self .deleteLeastRecently() } self .addRecently(key, value) } } extension LRUCache { private func makeRecently (_ key: Int) { if let node = hashMap[key] { cache.remove(node) cache.addLast(node) } } private func addRecently (_ key: Int,_ value: Int) { let node = Node (key, value) cache.addLast(node) hashMap[key] = node } private func deleteKey (_ key: Int) { if let node = hashMap[key] { cache.remove(node) hashMap[key] = nil } } private func deleteLeastRecently () { if let first = cache.removeFirst() { hashMap[first.key] = nil } } }
上述代码的关键是添加缓存和删除缓存的时候,要提升相应的缓存节点顺序。也就是要挪到双向列表的末尾。
LRU 缓存算法的核心策略是哈希表和双向列表的组合使用。
后记 我是穆哥,卖码维生的一朵浪花。我们下回见。