//
// LRUCache.swift
// LRUCache
//
// Created by wangjin on 2021/10/27.
//
//LRU（ Least Recently Used 最近使用过数据）
//目的：计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置，解决删除哪些数据的算法
//算法核心：双向链表和哈希表的结合体。是让时间复杂度为 O(1)
//工作流程：缓存淘汰策略
//大体思想：
//1.设置一个最大容量 capacity
//2.实现两个接口 一个是 put(key,val)方法 存入键值 一个是get(key) 方法取出对应val
//3.cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。
///代码 步骤：
///1.创建一个双链表节点
class Node {
/// 存时候的key string类型
var key : String?
/// 存的值 任意值
var val : Any?
/// 下一个节点
var next : Node?
/// 上一个节点
var prev : Node?
/// 节点初始化 传入 key 和val
init(key:String?,val:Any?) {
self.key = key
self.val = val
}
}
/// 创建一个双链表
class DoubleList {
/// 头尾虚节点
/// 头节点
var head : Node?
/// 尾节点
var tail : Node?
/// 链表长度
var size : Int = 0
init() {
head = Node(key: nil, val: nil)
tail = Node(key: nil, val: nil)
size = 0
/// 头指尾 尾指头 循环起来
head?.next = tail
tail?.next = head
}
/// 链表头部添加节点 node
func addFirst(node:Node) {
/// 这个得自己画图
/// 当前节点下一个 指向 头节点下一个
/// 当前节点上一个 指向头节点
/// 头节点下一个节点的上一个节点 指向当前节点
/// 头节点下一个节点 指向当前节点
node.next = head?.next
node.prev = head
head?.next?.prev = node
head?.next = node
/// 元素数加1
size += 1
}
/// 删除链表中某个节点 node 必须有节点
func removeNode(node:Node){
///这个自己画
node.prev?.next = node.next
node.next?.prev = node.prev
/// 元素减1
size -= 1
}
/// 删除最后一个节点 并返回该节点
func removeLast() -> Node? {
if size == 0 {
return nil
}
let last = tail?.prev
removeNode(node:last!)
return last
}
}
public class LRUCache {
/// 哈希map
private var map : [String? : Node?]
/// 双向链表
private var doubleList : DoubleList
/// 最大容量 传入
private var capacity : Int
init(capacity : Int) {
self.capacity = capacity
self.map = [:]
self.doubleList = DoubleList.init()
}
public func get(key : String) -> Any? {
if map[key] == nil {
return nil
}
let val = (map[key] as? Node)?.val
//这里是为了把数据提前
put(key: key, val: val)
return val
}
public func put(key:String,val:Any?) {
let node = Node.init(key: key, val: val)
if map[key] != nil {
//删除旧节点
doubleList.removeNode(node: (map[key] as? Node)!)
//插入新节点
doubleList.addFirst(node: node)
//更新map数据
map[key] = node
}else {
if capacity == doubleList.size {
//删除最后一个节点
guard let last = doubleList.removeLast() else {
return
}
map.removeValue(forKey: last.key)
}
// 添加到头部
doubleList.addFirst(node: node)
//更新map
map[key] = node
}
}
}
下面是调用
import UIKit
class ViewController: UIViewController {
override func viewDidLoad() {
super.viewDidLoad()
// Do any additional setup after loading the view.
let cache = LRUCache.init(capacity: 2)
cache.put(key: "1", val: 1)
cache.put(key: "2", val: 2)
let val = cache.get(key: "1")
print(val)
cache.put(key: "3", val: 3)
let val2 = cache.get(key: "2")
print(val2)
}
}
结果
image.png
