雙向鏈表+Map實(shí)現(xiàn)，get或悲、put镐作、時間復(fù)雜度為O(1).
LRU數(shù)據(jù)結(jié)構(gòu)如下圖：
LRU數(shù)據(jù)結(jié)構(gòu)，該圖來自https://marcosantadev.com/implement-cache-lru-swift/#cache_lru
LRU
LRU(least recently used) 最近最少使用的 隆箩，核心思想：如果數(shù)據(jù)最近被訪問该贾，將來被訪問的概率也高
步驟：
1.新插入數(shù)據(jù)放在表頭
2.最近訪問數(shù)據(jù)移動到表頭
3.當(dāng)鏈表滿了，就將尾部數(shù)據(jù)丟棄
代碼實(shí)現(xiàn)
// MARK: 輸出打印
protocol Printable {
func reversePrint()
func printf()
}
/// 鏈表節(jié)點(diǎn)
class LinkNode<T> {
var value: T
var next: LinkNode? = nil // 下一個節(jié)點(diǎn)
weak var previous: LinkNode? = nil // 前一個節(jié)點(diǎn)
init(_ value: T) {
self.value = value
}
}
// MARK: LRU緩存實(shí)現(xiàn)（雙向鏈表+map）
final class LRUCache<Key, Value> {
private struct CachePaylaod {
var key: Key
var value: Value
}
private typealias Node = LinkNode<CachePaylaod>
private var _head: Node?
private var _tail: Node?
private var _count: Int = 0
var count: Int {
return _count
}
private var _initCapacity: Int
private var _lruMap: [Key: LinkNode<CachePaylaod>]
init(_ capacity: Int) {
self._initCapacity = max(0, capacity)
_lruMap = [Key: LinkNode<CachePaylaod>].init(minimumCapacity: capacity)
}
/// 取值
func get(_ key: Key) -> Value? {
if let node = self._lruMap[key] {
self.moveNodeToHead(node: node)
}
return self._lruMap[key]?.value.value
}
/// 設(shè)置值
func put(_ key: Key, _ value: Value) {
let cachePayload = CachePaylaod.init(key: key, value: value)
/*
1捌臊、key 存在杨蛋，更新value,并將當(dāng)前節(jié)點(diǎn)移到鏈表頭部
2、key不存在，創(chuàng)建新的節(jié)點(diǎn)并拼接到頭部
3逞力、超過最大容量曙寡，移除最后一個節(jié)點(diǎn)
*/
if let node = self._lruMap[key] {
node.value = cachePayload
moveNodeToHead(node: node)
}else {
let node = LinkNode.init(cachePayload)
appenToHead(newNode: node)
_lruMap[key] = node
}
if _count > _initCapacity {
let nodeRemove = removeLastNode()
if let key = nodeRemove?.value.key {
_lruMap[key] = nil
}
}
}
/// 將存在的節(jié)點(diǎn)移到頭部
private func moveNodeToHead(node: Node) {
if node === _head {
return
}
let next = node.next
let previous = node.previous
if previous === _head {
previous?.previous = node
}
if node === _tail {
_tail = previous
}
previous?.next = next
next?.previous = previous
node.previous = nil
node.next = _head
_head?.previous = node
_head = node
}
/// 拼接一個新的節(jié)點(diǎn)到頭部
private func appenToHead(newNode: Node) {
if _head == nil {
_head = newNode
_tail = _head
}else{
let temp = newNode
temp.next = _head
_head?.previous = temp
_head = temp
}
_count += 1
}
/// 移除最后一個節(jié)點(diǎn)
@discardableResult
private func removeLastNode() -> Node? {
if let tail = _tail {
let tailPre = tail.previous
tail.previous = nil
tailPre?.next = nil
_tail = tailPre
if _count == 1 {
_head = nil
}
_count -= 1
return tail
}else {
return nil
}
}
}
extension LRUCache: Printable {
func reversePrint() {
var node = _tail
var ll = [Value]()
while node != nil {
ll.append(node!.value.value)
node = node?.previous
}
print(ll)
}
func printf() {
var node = _head
var ll = [Value]()
while node != nil {
ll.append(node!.value.value)
node = node?.next
}
print(ll)
}
}
測試：
let lru = LRUCache<Int, Int>.init(3)
lru.put(1, 1)
lru.put(2, 2)
lru.printf() 打印結(jié)果：[2, 1]
lru.reversePrint() 打印結(jié)果：[1, 2]
lru.get(1)
lru.printf() 打印結(jié)果：[1, 2]
lru.reversePrint() 打印結(jié)果：[2, 1]
lru.put(3, 3)
lru.printf() 打印結(jié)果：[3, 1, 2]
lru.reversePrint() 打印結(jié)果：[2, 1, 3]
lru.get(2)
lru.printf() 打印結(jié)果：[2, 3, 1]
lru.reversePrint() 打印結(jié)果：[1, 3, 2]
lru.put(4, 4)
lru.printf() 打印結(jié)果：[4, 2, 3]
lru.reversePrint() 打印結(jié)果：[3, 2, 4]
lru.get(1) 結(jié)果為nil
lru.printf() 打印結(jié)果：
lru.reversePrint() 打印結(jié)果：
lru.get(3)
lru.printf() 打印結(jié)果：[3, 4, 2]
lru.reversePrint() 打印結(jié)果：[2, 4, 3]
lru.get(4)
lru.printf() 打印結(jié)果：[4, 3, 2]
lru.reversePrint() 打印結(jié)果：[2, 3, 4]
lru.put(3, 30)
lru.printf() 打印結(jié)果：[30, 4, 2]
lru.reversePrint() 打印結(jié)果：[2, 4, 30]
題外話
該代碼實(shí)現(xiàn)leetcode居然編譯報(bào)錯??。不知道是不是泛型的影響寇荧。
雖然得到權(quán)威的認(rèn)證举庶，不過我堅(jiān)信這個實(shí)現(xiàn)沒問題??。
當(dāng)然揩抡，如有問題歡迎各路大神指點(diǎn)??户侥。
