使用Swift实现的LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

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)
        }
    }

    /// 超出容量移除最长没有使用的节点
    func checkSize() {
        if hashMap.count == capacity {
            if let deleteNode = head.next, let key = deleteNode.key {
                hashMap.removeValue(forKey: key)
                delete(node: deleteNode)
            }

        }
    }

    // 移除节点
    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>) {
        // 更新将节点移动到最后
        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
        }
    }
}