题目描述

解题思路

本题主要思路是使用 双向链表 + hash表 来实现，把最近使用的缓存放在链表头，而链表尾就是最久未使用的缓存，所以删除的时候将链表尾删除，如果新增或者操作过的数据，应该放在链表头。

使用Java自带的LinkedHashMap(不推荐)

// 使用提供的LinkedHashMap实现
class LRUCache extends LinkedHashMap<Integer, Integer> {
    int capacity = 0;
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

手动实现双向链表+hash表

步骤：

注意：使用虚拟头节点可以更加方便的找到最后一个节点和第一个节点，从而进行删除和插入。

class LRUCache extends LinkedHashMap<Integer, Integer> {
    // 构造双向链表
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {
        }
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 初始化变量
    Map<Integer, DLinkedNode> map;
    DLinkedNode head, tail;  // 首尾虚拟头节点
    int size = 0;
    int capacity = 0;
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        // 初始化虚拟头尾节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLinkedNode dLinkedNode = map.get(key);
        if (dLinkedNode == null) {
            // 不存在直接返回-1
            return -1;
        }
        // 如果key存在，移动到头部
        moveToHead(dLinkedNode);
        return dLinkedNode.value;
    }
    public void put(int key, int value) {
        DLinkedNode dLinkedNode = map.get(key);
        if (dLinkedNode == null) {
            // 不存在，需要构建并放入头部
            DLinkedNode node = new DLinkedNode(key, value);
            addHead(node);
            // 哈希表中也放入映射关系
            map.put(key, node);
            size++;
            // 此时如果容量超过限定值，需要删除尾部元素
            if (size > capacity) {
                DLinkedNode tailPrevNode = removeTail();
                // 删除hash表
                map.remove(tailPrevNode.key);
                size--;
            }
        } else {
            // 如果存在，修改值并移动到头部
            dLinkedNode.value = value;
            moveToHead(dLinkedNode);
        }
    }
    // 加入头部
    public void addHead(DLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    // 移动到头部
    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addHead(node);
    }
    // 删除指定节点
    public void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // 删除尾部节点
    public DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
}