Swift实现LRU缓存淘汰算法-白红宇

LRU = Least Recently Used，最近最少使用

使用的数据结构：链表，哈希表

使用的编程语言：Swift

思路描述：

维护一个有序链表（我使用的双向链表）
- 靠近尾部的节点则在时间上越早被访问

当有新数据时，先从头开始遍历链表
- 如果数据已经在缓存中
  - 遍历后得到数据所在的结点，从这个位置删除
  - 最后插入到链表头部
- 如果数据没在缓存中，再次分为两种情况
  - 如果缓存的空间没有满
    - 直接把这个数据所在的结点插入到链表头部
  - 如果缓存空间已满
    - 先删除尾结点
    - 把新数据的结点插入到链表头部（这个思路不包含哈希表）

一些细节

此次练习实现LRU缓存算法的目的：熟悉链表的代码实现，具体实现的是双向链表

使用链表的同时，也使用了哈希表：
- 如果不使用哈希表
  - 由于每当有新数据时都要遍历一次链表，时间复杂度为O(n)
- 如果包含哈希表
  - 每当有新数据时，由于可以查询数据是否存在哈希表里，时间复杂度降至O(1)
  - 这里使用了空间换时间的思想

使用链表实现的缺点
- 1）内存空间消耗更大，因为需要额外的空间存储指针信息。
- 2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

使用数组实现的缺点
- 1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
- 2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

具体代码（基于链表和哈希表）

链表：

// 节点public class LinkedListNode
    
      {        var key: K?    var value: V?    var next: LinkedListNode?    weak var previous: LinkedListNode?        public init(key: K? ,value: V?) {        self.key = key        self.value = value    }}// 双向链表class LinkedList
     
       : NSObject {        public typealias Node = LinkedListNode
      
               // 头节点，私有    private var head: Node?        // 获取链表第一个元素    public var first: Node? {        return head    }        // 获取链表最后一个元素    public var last: Node? {                guard var node = head else {            return nil        }                while let next = node.next {            node = next        }        return node    }            // 检查链表是否为空    public var isEmpty: Bool {        return head == nil    }            // 获取链表的长度    public var count: Int {                guard var node = head else {            // head为nil，空链表            return 0        }                // 循环，知道node为nil为止        var count = 1        while let next = node.next {            node = next            count += 1        }        return count    }            // 在指定的index获取node    public func node(atIndex index: Int) ->Node? {                guard index != 0 else {            // 是head            return head        }                var node = head!.next                guard index < 0 else {            return nil        }                for _ in 1..
       
         V? {        guard !isEmpty else {            return nil        }        return remove(node: last!)    }            // 删除指定的元素    public func remove(node: Node) -> V? {                guard head != nil else {            print("链表为空")            return nil        }                        let prev = node.previous        let next = node.next                        if let prev = prev {            prev.next = next        } else {            head = next        }                        next?.previous = prev                node.previous = nil        node.next = nil                return node.value    }            // 删除指定index的元素    public func removeAt(_ index: Int) -> V? {                guard head != nil else {            print("linked list is empty")            return nil        }                let node = self.node(atIndex: index)        guard node != nil else {            return nil        }        return remove(node: node!)    }}复制代码

LRU缓存算法：

class LRUStrategy
    
     : NSObject {    let capacity: Int    var length = 0        private let queue: LinkedList
     
          private var hashtable: [K: LinkedListNode
      
       ]            /*      LRU（Least Recently Used） Cache, 		capacity是确定缓存的最大值     */    init(capacity: Int) {        self.capacity = capacity                self.queue = LinkedList()        self.hashtable = [K: LinkedListNode
       
        ](minimumCapacity: self.capacity)    }        // swift的下标语法，在这是LRUStrategy类哈希化后，get set的语法糖    subscript (key: K) -> V? {        get {            if let node = self.hashtable[key] {                _ = self.queue.remove(node: node)                self.queue.insertToHead(node: node)                return node.value            } else {                return nil            }        }                set(value) {            if let node = self.hashtable[key] {                node.value = value                                _ = self.queue.remove(node: node)                self.queue.insertToHead(node: node)            } else {                let node = LinkedListNode(key: key, value: value)                                if self.length < capacity {                    // 队列还没有满                    self.queue.insertToHead(node: node)                    self.hashtable[key] = node                                        self.length = self.length + 1                } else {                    // 队列满了                    self.hashtable.removeValue(forKey: self.queue.last!.key!)                    _ = self.queue.removeLast()                                        if let node = self.queue.last {                        node.next = nil                    }                                        self.queue.insertToHead(node: node)                    self.hashtable[key] = node                }            }        }    }}复制代码