使用Swift實(shí)現(xiàn)的LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

public class LruCache3<K:Hashable, V> {
    private let capacity: Int
    private var hashMap: [K: ListNode<K, V>]
    private let head: ListNode<K, V>
    private let tail: ListNode<K, V>

    init(_ capacity: Int) {
        self.capacity = capacity
        self.hashMap = [K: ListNode<K, V>]()
        head = ListNode(nil, nil)
        tail = ListNode(nil, nil)
        head.next = tail
        tail.prev = head
    }

    func get(_ key: K) -> V? {
        guard let oldNode = hashMap[key] else {
            return nil
        }
        updateNode(oldNode: oldNode)
        return oldNode.val
    }

    func put(_ key: K, _ value: V) {

        if let oldNode = hashMap[key] {
            oldNode.val = value
            updateNode(oldNode: oldNode)
        } else {
            checkSize()
            let newNode = ListNode(key, value)
            hashMap[key] = newNode
            addAtLast(node: newNode)
        }
    }

    /// 超出容量移除最長沒有使用的節(jié)點(diǎn)
    func checkSize() {
        if hashMap.count == capacity {
            if let deleteNode = head.next, let key = deleteNode.key {
                hashMap.removeValue(forKey: key)
                delete(node: deleteNode)
            }

        }
    }

    // 移除節(jié)點(diǎn)
    private func delete(node: ListNode<K, V>) {
        // 移除
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    /// 將最新的添加到最后
    private func addAtLast(node: ListNode<K, V>) {
        let prev = tail.prev
        // 添加到新的位置
        prev?.next = node
        node.prev = prev

        node.next = tail
        tail.prev = node
    }

    private func updateNode(oldNode: ListNode<K, V>) {
        // 更新將節(jié)點(diǎn)移動到最后
        delete(node: oldNode)
        addAtLast(node: oldNode)
    }

    private class ListNode<K:Hashable, V> {
        public var val: V?
        public var key: K?
        public var next: ListNode?
        public var prev: ListNode?
        public init(_ key: K?, _ val: V?) {
            self.key = key
            self.val = val
            self.next = nil
        }
    }
}