如何用 Swift 来实现一个 LRU 缓存呢?

计算机的缓存容量是有限的,当缓存满的时候,我们需要删除旧数据,给新的数据腾出位置。
那么问题来了,我们应该删除哪些数据呢?也就是说应该使用哪种缓存策略呢?

LRU(Least Recently Used)就是其中一种缓存淘汰策略。LRU 认为最近使用过的缓存是有用的,缓存满了应该优先删除那些没使用过的。

思路

LRU 缓存主要的操作方法是 putgetput 用于增加缓存,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 {
/// 提升 key 对应的缓存节点
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
}

/// 删除 key 对应的缓存节点
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 缓存算法的核心策略是哈希表和双向列表的组合使用。

后记

我是穆哥,卖码维生的一朵浪花。我们下回见。