此文章为本人翻译的译文，版权为原作者所有。
英文原文：How To Implement Cache LRU With Swift
本文代码地址MarcoSantarossa/CacheLRU.swift，个人觉得本文的实现不是很好，我写了新的版本，戳这里LRUCache
介绍
Cache LRU（最近最少使用）和字典很相似。通过Key-Value的方式存储。字典和Cache之间的区别在于后者的容量有限。每次达到容量时，Cache都会删除最近最少使用的数据。
在本文中，我们将看看如何使用Swift实现Cache LRU。
内容
- 入门指南
- 双链表
- Cache LRU
- 总结
入门指南
首先，我们必须了解应该用什么数据结构来实现Cache LRU。有不同的方式来实现它。在这个版本中使用：
- 双链表：这是核心。我们需要这个链表来缓存元素。不使用数组，因为它更慢。Cache LRU策略是每次把最近使用的元素移到头部。但是如果我们将数组中的元素移到数组中的索引0处，需要对所有其他元素执行右移。
-
Dictionary<Key, ListNode>：使用双链表的问题是它的查找的时间复杂度是O（n）。可以使用一个字典来解决这个瓶颈 - 它的查找时间复杂度是O（1）。我们使用这个字典来存储列表的节点。
在下一节中，将看到如何实现双链表。如果你已经知道了，可以直接跳到Cache LRU部分。
双链表
对于本文，我们不需要实现完整的双向链表。 出于这个原因，只实现Cache中使用到的的方法。
第一步是创建一个类DoublyLinkedList，它接受一个泛型T来存储节点：
final class DoublyLinkedList<T> {
}
然后为节点创建一个类：
final class DoublyLinkedList<T> {
final class Node<T> {
var payload: T
var previous: Node<T>?
var next: Node<T>?
init(payload: T) {
self.payload = payload
}
}
}
在这里使用一个嵌套的Node类。 如果你使用的是早于3.1的Swift版本，则必须在DoublyLinkedList之外创建此类。 Swift 3.1支持具有泛型的嵌套类。
然后，设置链表的存储最大量：
private(set) var count: Int = 0
链表上的操作有时实现起来很困难。可以存储第一个和最后一个元素，让一切更轻松：
private var head: Node<T>?
private var tail: Node<T>?
现在开始实现链表中的方法：
addHead
我们需要一个向链表中添加新元素的方法，这个新元素就是最近使用的元素。
func addHead(_ payload: T) -> Node<T> {
let node = Node(payload: payload)
defer {
head = node
count += 1
}
guard let head = head else {
tail = node
return node
}
head.previous = node
node.previous = nil
node.next = head
return node
}
moveToHead
Cache LRU需要我们将最近使用的元素放在列表头部。 因此需要一个方法把节点移动到头部：
func moveToHead(_ node: Node<T>) {
guard node !== head else { return }
let previous = node.previous
let next = node.next
previous?.next = next
next?.previous = previous
node.next = head
node.previous = nil
if node === tail {
tail = previous
}
self.head = node
}
removeLast
当Cache已满时，需要一个方法来删除最久未使用的元素
func removeLast() -> Node<T>? {
guard let tail = self.tail else { return nil }
let previous = tail.previous
previous?.next = nil
self.tail = previous
if count == 1 {
head = nil
}
count -= 1
// 1
return tail
}
-
tail的值与self.tail不同。
最后，可以为Node类型添加一个别名，以便在Cache实现中使用：
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>
链表实现的最终版本应该是这样的：
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>
final class DoublyLinkedList<T> {
final class Node<T> {
var payload: T
var previous: Node<T>?
var next: Node<T>?
init(payload: T) {
self.payload = payload
}
}
private(set) var count: Int = 0
private var head: Node<T>?
private var tail: Node<T>?
func addHead(_ payload: T) -> Node<T> {
let node = Node(payload: payload)
defer {
head = node
count += 1
}
guard let head = head else {
tail = node
return node
}
head.previous = node
node.previous = nil
node.next = head
return node
}
func moveToHead(_ node: Node<T>) {
guard node !== head else { return }
let previous = node.previous
let next = node.next
previous?.next = next
next?.previous = previous
node.next = head
node.previous = nil
if node === tail {
tail = previous
}
self.head = node
}
func removeLast() -> Node<T>? {
guard let tail = self.tail else { return nil }
let previous = tail.previous
previous?.next = nil
self.tail = previous
if count == 1 {
head = nil
}
count -= 1
return tail
}
}
Cache LRU
现在是时候实现Cache了。 我们可以开始创建一个新的CacheLRU类：
泛型Key必须是Hashable类型，因为它是存储在双链表中的值的key。
Cache和字典一样是通过Key-Value方式存储数据。不幸的是，我们的双链表值只能是payload，而不能是一个key。 为了解决这个问题，可以创建一个包含value和key的结构体。链表节点将存储包含value和key的对象CachePayload：
final class CacheLRU<Key: Hashable, Value> {
private struct CachePayload {
let key: Key
let value: Value
}
}
然后，我们应该添加两个数据结构 - 一个双链表和一个字典：
private let list = DoublyLinkedList<CachePayload>()
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()
正如在介绍中看到的那样，Cache LRU的容量有限。 我们可以通过init方法把容量传给一个私有属性：
private let capacity: Int
init(capacity: Int) {
self.capacity = max(0, capacity)
}
使用max方法来避免capacity小于0。
现在实现两个Cache方法来get和set元素：
setValue
通过set方法，可以为某个key添加/更新元素。这个值作为最近使用的元素移动到链表的开头：
func setValue(_ value: Value, for key: Key) {
// 1
let payload = CachePayload(key: key, value: value)
// 2
if let node = nodesDict[key] {
node.payload = payload
list.moveToHead(node)
} else {
let node = list.addHead(payload)
nodesDict[key] = node
}
// 3
if list.count > capacity {
let nodeRemoved = list.removeLast()
if let key = nodeRemoved?.payload.key {
nodesDict[key] = nil
}
}
}
- 创建一个对象来包装要存储在列表中的
key和value。 - 如果链表已经存储了该特定key的元素，更新该值并将其移动到列表的开头。否则，创建一个新节点并将其添加为列表的头部。
- 如果超过了Cache容量，删除链表最后一个元素。
getValue
使用get方法，可以拿到特定key的元素。 每次使用一个元素时，它都会作为最近使用的元素移动到链表的头部：
func getValue(for key: Key) -> Value? {
guard let node = nodesDict[key] else { return nil }
list.moveToHead(node)
return node.payload.value
}
Cache最终版本是这样的：
final class CacheLRU<Key: Hashable, Value> {
private struct CachePayload {
let key: Key
let value: Value
}
private let capacity: Int
private let list = DoublyLinkedList<CachePayload>()
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()
init(capacity: Int) {
self.capacity = max(0, capacity)
}
func setValue(_ value: Value, for key: Key) {
let payload = CachePayload(key: key, value: value)
if let node = nodesDict[key] {
node.payload = payload
list.moveToHead(node)
} else {
let node = list.addHead(payload)
nodesDict[key] = node
}
if list.count > capacity {
let nodeRemoved = list.removeLast()
if let key = nodeRemoved?.payload.key {
nodesDict[key] = nil
}
}
}
func getValue(for key: Key) -> Value? {
guard let node = nodesDict[key] else { return nil }
list.moveToHead(node)
return node.payload.value
}
}
我们可以像这样使用这个Cache：
let cache = CacheLRU<Int, String>(capacity: 2)
cache.getValue(for: 5) // nil
cache.setValue("One", for: 1)
cache.setValue("Eleven", for: 11)
cache.setValue("Twenty", for: 20)
cache.getValue(for: 1) // nil. We exceeded the capacity with the previous `setValue` and `1` was the last element.
cache.getValue(for: 11) // Eleven
总结
这就是我们的Cache LRU了。
如今，我们应用程序有很多内存可用。 尽管如此，可能仍需要一个容量有限的缓存来节省内存空间。例如，当我们必须缓存像图像那样耗费空间的对象时。
Update:
我发现Array比链表快。因为Cache LRU的版本使用双链表，所以我抛弃了这种的作法。
