LRU和LFU是两种经典的缓存策略，实现复杂度也适中，非常适合用来面试考察中级以上的开发者，日常练手也是非常有益的。
说明和应用
LRU
LRU(Least Recently Used)策略是淘汰最旧的缓存，典型的应用场景就是手机上的App使用列表历史。
当一个已经打开过的App被用户再次使用时，此App会提升到最新的缓存，不会被缓存策略淘汰掉。
而太久没有使用的App，则会在需要清除缓存释放资源时被首先淘汰。
LFU
LFU(Least Frequently Used)策略是淘汰使用频率最低的缓存，典型的应用场景是代理的缓存系统。Cache优先缓存高频请求的资源，而将低频内容淘汰掉，这样缓存就可以很好的提升代理速度效果。
原理
LRU策略比较直观和简单，本质上需要解决的问题是两点：
* 缓存查找性能
* 缓存的增、删、改性能，而且要求缓存有序
最快的查找必然是哈希表，增、删、改性能最好的是双向链表，所以LRUCache的底层数据结构就是哈希表和双链表，结合这两个数据结构的优点解决两个问题。
所以实现LRU的数据结构如下：
1. 通过哈希表解决查找性能
2. 通过双链表解决缓存管理性能
LFU策略和LRU相比，在淘汰缓存时，多了一个查找维度：频率。
所以查找时，依旧要处理查找频率的问题。缓存的增、删、改性能以及优秀，和LRU相同，所以依旧通过双链表来解决。
LFU策略中，会出现同一频率下的缓存淘汰。淘汰策略可以根据具体应用场景来设计，但是最朴素的就是进行LRU淘汰。
所以实现LRU的数据结构如下：
1. 通过哈希表解决查找性能
2. 增加频率维度的哈希表解决频率维度的查找性能
2. 通过双链表解决缓存管理性能
实现
LRU
- 通过valueMap保存key-Cache，Cache则包装到链表的Node中
- 通过一个双链表管理Cache的有序问题（Recently Used）
以下是LRU的实现，不包含相关的protocol和泛型以及层次设计。完整实现在这里
class NaiveLRUCache<NaiveLRUCacheKey: Hashable, NaiveLRUCacheValue>: BaseCache {
typealias ValueNodeType = CacheListNode<NaiveLRUCacheKey, NaiveLRUCacheValue>
private var valueMap: [NaiveLRUCacheKey: ValueNodeType] = [:]
private var list: DLinkedList<ValueNodeType>
init() {
let default_capacity: Int = 5
list = DLinkedList<ValueNodeType>()
super.init(default_capacity)
}
init(capacity: Int) {
list = DLinkedList<ValueNodeType>()
super.init(capacity)
}
var count: Int {
return valueMap.count
}
public func setValue(_ value: NaiveLRUCacheValue, forKey key: NaiveLRUCacheKey) {
if cache_size <= 0 {
return
}
lock.lock()
if let node = valueMap[key] {
//有缓存，更新value
node.val = value
//移除旧缓存，放到最新
list.removeNode(node)
list.appendNode(node)
} else {
//无缓存，增加node
let n = CacheListNode<NaiveLRUCacheKey, NaiveLRUCacheValue>(key, value)
valueMap[key] = n
list.appendNode(n)
}
lock.unlock()
//检查是否超出容量，则移除最旧的缓存
clean()
}
public func value(forKey key: NaiveLRUCacheKey) -> NaiveLRUCacheValue? {
lock.lock()
defer { lock.unlock() }
if let v:CacheListNode = valueMap[key] {
//移除缓存然后再放到最新
list.removeNode(v)
list.appendNode(v)
return v.val
}
return nil
}
@discardableResult
public func removeValue(forKey key: NaiveLRUCacheKey) -> Bool {
lock.lock()
defer { lock.unlock() }
guard let v:CacheListNode = valueMap.removeValue(forKey: key) else {
return false
}
list.removeNode(v)
return true
}
private func clean() {
lock.lock()
defer { lock.unlock() }
while count > cache_size, let h = list.head {
//删除最旧缓存
list.removeNode(h)
valueMap.removeValue(forKey: h.key)
}
}
}
LFU
- 和LRU一样，通过valueMap保存key-Cache，Cache则包装到链表的Node中
- 在节点中增加freq字段管理缓存频率
- 通过freqMap保存freq-CacheList，即同一频率的缓存node都收纳到一个链表中，这个链表通过freqMap来索引
- LFU比LRU多的操作有几点：
- 当缓存的频率变更时，需要处理缓存node换到新链表的问题
- 淘汰缓存的时候，需要处理该频率对应的链表为空的问题。这个问题展开又可以说很多：）
- 如果不删除，则会一直占用内存，最坏情况下，freqMap的内存开销和cache数量一致(每个cache的频率都不一致）；
- 如果频繁删除，则会有大量的内存分配动作带来的开销。
所以光是freqMap的清洁操作都可以有很多种处理方式，要结合具体的Cache应用场景，Cache的内容来设计。
这里的实现是当链表为空的时候，删掉freqMap中的freq-List对。
以下是LFU的实现，不包含相关的protocol和泛型以及层次设计。完整实现在这里
extension NaiveLFUCache {
class NaiveLFUCacheValueNode: CacheListNode<NaiveLFUCacheKey, NaiveLFUCacheValue> {
var freq: Int = 0
override init(_ k: NaiveLFUCacheKey, _ v: NaiveLFUCacheValue) {
super.init(k, v)
}
public func useCount() {
freq += 1
}
}
}
class NaiveLFUCache<NaiveLFUCacheKey: Hashable, NaiveLFUCacheValue>: BaseCache {
typealias ValueNodeType = NaiveLFUCacheValueNode
typealias ValueListType = DLinkedList<ValueNodeType>
private var valueMap: [NaiveLFUCacheKey: ValueNodeType] = [:] // <key, value wrap in Node with freq>
private var freqMap: [Int: ValueListType] = [:] // <freq, List>
private var minFreq = 1
init() {
let default_capacity: Int = 5
super.init(default_capacity)
}
init(capacity: Int) {
super.init(capacity)
}
var count: Int {
return valueMap.count
}
private func resettleNode(_ node: ValueNodeType) {
node.useCount()
if node.freq <= minFreq {
minFreq = node.freq
}
if let freqList = freqMap[node.freq] {
freqList.appendNode(node)
} else {
//出现了新的频率
let newlist = ValueListType()
newlist.appendNode(node)
freqMap[node.freq] = newlist
}
}
public func setValue(_ value: NaiveLFUCacheValue, forKey key: NaiveLFUCacheKey) {
if cache_size <= 0 {
return
}
lock.lock()
if let node = valueMap[key] {
//有缓存，更新value
node.val = value
if let freqList = freqMap[node.freq] {
freqList.removeNode(node)
if freqList.isEmpty {
freqMap.removeValue(forKey: node.freq)
}
}
resettleNode(node)
} else {
//无缓存，新增
//新增之前检查容量，检查是否超出容量，否则移除最旧的缓存
tryToRetireTheLeastUsedNode()
let node = NaiveLFUCacheValueNode(key, value)
valueMap[key] = node
resettleNode(node)
}
lock.unlock()
}
public func value(forKey key: NaiveLFUCacheKey) -> NaiveLFUCacheValue? {
lock.lock()
defer { lock.unlock() }
if let node = valueMap[key] {
//存在
//从旧频率表中移除
if let oldFreqList = freqMap[node.freq] {
oldFreqList.removeNode(node)
if oldFreqList.isEmpty {
freqMap.removeValue(forKey: node.freq)
}
}
resettleNode(node)
return node.val
}
return nil
}
private func tryToRetireTheLeastUsedNode() {
while count >= cache_size {
//删除最少使用（频率最低）且最旧缓存
if let list = freqMap[minFreq], !list.isEmpty, let h = list.head {
list.removeNode(h)
valueMap.removeValue(forKey: h.key)
if list.isEmpty {
freqMap.removeValue(forKey: minFreq)
}
} else {
freqMap.removeValue(forKey: minFreq)
minFreq += 1
}
}
}
}
总结
LRU和LFU缓存策略的实现，是很好的数据结构应用学习。
将常用的重要的两个基础数据结构都覆盖到了，在LFU中还可以进一步探讨内存管理的sense和理解。而且，除了考察数据结构的掌握情况，还可以展开去考察多线程问题。
关于线程安全，有两个解决思路
1、直接用锁，这个是最容易想到的办法。但是一不小心会搞出死锁来，要小心。
2、用串行队列再封一层，把所有需要上锁的行为，都通过队列串行化
但可能需要调整代码，以确保一些行为进队列后依旧可以保证是紧挨着直行的，而不会被其他线程插入的任务打断
我面试的话，如果候选人可以把LRU和LFU理解和实现都搞清楚，基本上可以认为数据结构基础是没有问题的。
Refer
Leetcode: 146. LRU Cache
Leetcode: 460. LFU Cache