LRU缓存设计

设计要求

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

思考

要求	满足条件	对应数据结构
查找快	get时间复杂度为O(1)	哈希表
插入快	put时间复杂度为O(1)	链表
有顺序之分	区分最近使用的和久未使用的数据	链表
删除快	put时间复杂度为O(1)	双向链表

综上分析，需要双向链表和哈希表结合，形成哈希链表。

实现

首先设计双向链表：

• 节点类CacheNode

    class CacheNode {
        public var key : Int
        public var val : Int
        public var next, prev : CacheNode?
        init(_ k : Int, _ v : Int) {
            self.key = k
            self.val = v
        }
    }
  

• 双向链表

    class DoubleList {
        //头尾虚节点
        var head, tail : CacheNode?
        //链表元素数
        var size : Int = 0
          
        init() {
            head = CacheNode(0, 0)
            tail = CacheNode(0, 0)
            head?.next = tail
            tail?.prev = head
            size = 0
        }
          
        //在链表头部添加节点x
        public func addFirst(_ x : CacheNode) {
            x.next = head?.next
            x.prev = head
            head?.next?.prev = x
            head?.next = x
            size += 1
        }
          
        //删除链表中的节点（x一定存在）
        public func remove(_ x : CacheNode) {
            x.prev?.next = x.next
            x.next?.prev = x.prev
            size -= 1
        }
          
        //删除链表最后一个节点，并返回该节点
        public func removeLast() -> CacheNode? {
            if tail?.prev?.val == (head?.val)! {
                return nil
            }
            let last = tail?.prev
            remove(last!)
            return last
        }
          
        //返回链表长度
        public func Size() -> Int {
            return size
        }
    }
  

然后是设计哈希链表：

• LRU类

    class LRUCache {
          
        //哈希表
        var map: [Int : CacheNode?] = [:]
        //双向链表
        var cache: DoubleList
        //最大容量
        var cap: Int
      
        init(_ capacity: Int) {
            self.cap = capacity
            self.map = [:]
            self.cache = DoubleList()
        }
          
        func get(_ key: Int) -> Int {
            if map[key] == nil {
                return -1
            }
            let val = (map[key] as? CacheNode)!.val
            //利用put方法把数据提前
            put(key,val)
            return val
        }
          
        func put(_ key: Int, _ value: Int) {
            //先把新节点x做出来
            let x = CacheNode(key, value)
            if map[key] != nil {
                //删除旧节点
                cache.remove((map[key] as? CacheNode)!)
            } else {
                if cap == cache.Size() {
                    //删除链表最后一个节点
                    let last = cache.removeLast()
                    map.removeValue(forKey: (last?.key)!)
                }
            }
            //直接添加到头部
            cache.addFirst(x)
            //更新map数据
            map[key] = x
        }
    }
  

对于LRU类，有两个值得注意的点：

1. 在get方法中，如果一个数据之前已经记录过，需要用put方法更新最近
2. 在更新链表的同时，不要忘记更新map