如何用 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 {
    /// 提升 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 缓存算法的核心策略是哈希表和双向列表的组合使用。

后记

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