1. NSCache
class NSCache<KeyType, ObjectType> : NSObject where KeyType : AnyObject, ObjectType : AnyObject
NSCache 用于短暂地保存键值对，当系统资源不足时，系统会回收为这些键值对分配的空间
NSCache 与其他可修改的集合有以下几点区别：
- NSCache 内含了几种自动回收机制，用于确保 NSCache 不会过多地占有系统资源，当其他应用需要额外的内存时，这些机制会自动移除一些NSCache 中缓存的项目，使NSCache所占的内存空间达到最小化。
- 在不同的线程添加、移除或检索 NSCache 中的项目时，不需要我们手动地加锁。
- 与 NSMutableDictionary 不同的是，NSCache 不会复制放进 NSCache 中的键对象（Key）
使用NSCache时需要注意的点：
因为 NSCache 使用了自动回收机制，所以不适用于存储比较常用的，重新计算花销较大的数据。
此外自动回收内存时的，回收的顺序是不确定的，所以不能保证最先放进 NSCache 中的项目会被最先释放。
NSCache 中的Key和Value都必须是引用类型，所以Swift中的值类型(例如String)不能直接用在 NSCache 中，需要与OC中相应的类型(例如NSString)桥接后才能使用。
NSCache 常用的属性和方法：
.countLimit
NSCache 中应该存储的项目的数量上限，默认值为0（没有限制），该属性并不是一种严格的限制，当 NSCache 中的项目数量超过上限时，系统可能立刻、稍后或从不回收 NSCache 中项目，具体的回收时机取决于系统的回收机制。
.totalCostLimit
NSCache 在进行内存回收前，已占用的内存上限，默认值为0（没有限制），和上述一样，这不是一种严格的限制，具体的回收时机取决于系统的回收机制。
cache(NSCache<AnyObject, AnyObject>, willEvictObject: Any)
NSCacheDelegate 中的方法，在某一对象被释放时，该方法会被调用
object(forKey: KeyType) -> ObjectType?
根据Key检索相应的Value
setObject(ObjectType, forKey: KeyType) | setObject(ObjectType, forKey: KeyType, cost: Int)
将Key对应的Value存储到 NSCache 中
removeObject(forKey: KeyType) | removeAllObjects()
根据Key移除Cache中的Value或者移除Cache中的所有项目
通过单例模式简单地实现NSCache：
final class CacheAutoRelease {
// Shared instance
static let shared: CacheAutoRelease = CacheAutoRelease()
// Shared cache
private static let cache: NSCache<NSString, AnyObject> = {
let cache = NSCache<NSString, AnyObject>()
return cache
}()
private init(){}
// Save data to cache
func cache(object: AnyObject, key: String) {
CacheAutoRelease.cache.setObject(object, forKey: key as NSString)
}
// Retrive data from cache
func getFromCache(key: String) -> AnyObject? {
return CacheAutoRelease.cache.object(forKey: key as NSString)
}
}
2. 运用LRU策略实现缓存
LRU -- 最近最久未使用页面置换算法，常见于操作系统的内存管理，具体的思想是：当需要淘汰内存中的某一页面时，选择最近最久未被访问的页面换出，因为此算法认为最近最久未被访问的页面很可能在将来也不会被访问，所以淘汰该页面使得后续操作的开销最小（避免频繁的换入换出操作）。
我们可以将该算法的思想运用在缓存中，即分配一段内存空间作为缓存区，当缓存区空间不足时，淘汰缓存区中最近最久未被访问的项目，使得缓存区可以存放新的项目的同时，又避免了因淘汰会被经常访问的项目而带来的额外开销。
实现 LRU 算法最基本的方法是使用数组和时间戳（记录项目最近被访问的时间点），但在更新时间戳或者移除项目时，都需要遍历数组或移动数组元素，显然，该实现的时间复杂度太高，效率低下。所以我们一般使用 Dictionary（字典）和 Double Linked List （双向链表）两种数据结构实现 LRU 算法，使得查询、插入和删除项目的时间复杂度为常量，即O(1)。
使用双向链表时，我们将最近被访问过的项目移动到链表的头部，使得最近被访问过的项目都集中在链表的头部，而尾部则是那些最近最久未被访问的项目，所以删除项目时，就选择链表尾部的项目进行删除即可，而不需要通过保存或更新访问项目时的时间戳来决定哪些是最久最久未被访问的项目，提高了算法的效率。而字典用于保存链表中各项目的指针，所以查询项目时，直接到字典中查询，而不需要遍历链表，当然，更新链表中的任意项目（插入，删除，移动位置等操作），都需要相应地更新字典。
-
双向链表的实现
count- Cache可以保存的项目上限
head- 头指针
tail- 尾指针
addNewNode(_:) -> Node<T>- 在双向链表头部加入新的节点
removeLastNode() -> Node<T>- 去掉双向链表最后一个节点
moveToHead(_:)- 将节点移动到双向链表的头部
final class DoubleLinkedList<T> {
// Node used in double linked list
final class Node<T> {
var value: T
var previous: Node<T>?
var next: Node<T>?
init(value: T) {
self.value = value
}
}
// The maximum number of nodes that can be stored in the double linked list
private(set) var count: Int = 0
// The pointer for the head of double linked list
private var head: Node<T>?
// The pointer for the tail of double linked list
private var tail: Node<T>?
// Add new node to the head of double linked list
func addNewNode(_ value: T) -> Node<T> {
let node = Node(value: value)
// Alter the pointer of head and increase the amount of nodes after operation
defer {
head = node
count += 1
}
// When the double linked list is empty before, the pointer of tail also point at the new element
guard let head = head else {
tail = node
return node
}
head.previous = node
node.next = head
return node
}
// Remove the node which is at the tail of double linked list
func removeLastNode() -> Node<T>? {
guard let tail = tail else {
return nil
}
tail.previous?.next = nil
self.tail = tail.previous
// When there was only one node in the double linked list before, set up the pointer of head as nil,
// because it point at the same place as the pointer of tail do
count -= 1
if count == 0 {
head = nil
}
return tail
}
// Move the node which has been visited recently to the head of double linked list
func moveToHead(_ node: Node<T>) -> Void {
// Return when the node was already located in the head of double linked list
guard head !== node else {
return
}
// If the node locate in the tail of double linked list,
// then alter the pointer of tail and make it point at the previous node of current node
if tail === node {
tail = node.previous
}
node.previous?.next = node.next
node.next?.previous = node.previous
node.next = head
node.previous = nil
head?.previous = node
head = node
}
}
-
LRU缓存的实现
因为在删除双向链表中的节点时，我们还需要删除字典中对应的项目，所以为了方便，我们可以用一个额外的数据结构 CombinedValue 保存Key和Value，这样在删除节点时，通过节点中保存的Key，就可以方便地删除字典中的项目。
当往字典里存放新的值时，需要检测双向链表是否超出了容量的上限，若是，需要删除最近最久未被访问的节点。
同时，访问字典中的项目时，也需要对应的将双向链表中的节点移动到双向链表的头部
typealias DoubleLinkedListNode<T> = DoubleLinkedList<T>.Node<T>
final class LRUCache<Key: Hashable, Value> {
// Because we need to get the associated key of node when remove that node from double linked list,
// so we create a new structrue to bind the key with the value, and save it as the value of node
private struct CombinedValue {
let key: Key
let value: Value
}
// Data structure for LRUCache
private let list = DoubleLinkedList<CombinedValue>()
private var dict = Dictionary<Key, DoubleLinkedListNode<CombinedValue>>()
private var capacity: Int
init(capacity: Int) {
// The capacity is not allowed to be lower than 0
self.capacity = max(0, capacity)
}
func setValue(_ value: Value, for key: Key) -> Void {
// Create a new structrue to hold the key and value
let newCombinedValue = CombinedValue(key: key, value: value)
// If the node is already exist, update its value and move it to the head of double linked list, or add a new node to the double linked list
if let node = dict[key] {
node.value = newCombinedValue
list.moveToHead(node)
} else {
let newNode = list.addNewNode(newCombinedValue)
dict[key] = newNode
}
// When the total number of nodes in the double linked list exceeded the capacity of Cache,
// then remove the least recently used node which was the last node of double linked list
if list.count > capacity {
if let node = list.removeLastNode() {
dict[node.value.key] = nil
}
}
}
// Retrieve the value from dictionary
func value(for key: Key) -> Value? {
guard let node = dict[key] else {
return nil
}
// Move the node to the head of double linked list, so we mark it as the node visited recently
list.moveToHead(node)
return node.value.value
}
}
