题目描述

题解

双向哈希链表

题目要求查询和添加操作都是O(1)的时间复杂度, 链表进行增删操作能达到O(1), 哈希表的查询操作能达到O(1), 所以将两种数据结构进行结合.

既然是双向链表, 那么需要构造一个节点类Node, 它需要包含key值和value值, 并且还需要有前节点和后节点

哈希表中的key为节点的key, value存储的就是对应的节点Node 了.目的是为了通过key值直接获取该节点, 以此来高效完成频繁的查询操作

get()方法:

如果map中没有该元素, 直接返回-1
否则, 从map中查询到相应的值, 在返回之前还需要将该节点升到双向链表的首位, 这个过程与put() 方法逻辑相同, 直接将该键值对调用put方法即可

put(key, value)方法:

首先根据传入的(key, value)创建一个Node节点
如果map中包含该key, 那么缓存的大小不变, 将双向链表中的同键节点删除, 然后将新建的节点添加到链表的首位
如果不包含该key
- 如果当前缓存大小小于规定的容量, 直接将新建节点添加到链表首位
- 如果已经达到了规定的容量, 那么将链表的末位节点删除, 然后将新建节点添加到链表首位

public class LRUCache {

    private static class Node {
        int key;
        int value;
        Node pre, next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private static class DoubleLinked {

        Node head, tail;
        private int size = 0;

        public void addFirst(Node node) {
            if (head == null) {
                head = node;
                tail = node;
            } else {
                Node temp = head;
                temp.pre = node;
                node.next = temp;
                head = node;
            }
            size++;
        }

        public void remove(Node node) {
            if (node == head && node == tail) {
                head = null;
                tail = null;
            } else if (node == head) {
                node.next.pre = null;
                head = node.next;
            } else if (node == tail) {
                node.pre.next = null;
                tail = node.pre;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;

            }
            size--;
        }

        public Node removeLast() {
            Node temp = tail;
            remove(tail);
            return temp;
        }

        public int getSize() {
            return size;
        }
    }

    HashMap<Integer, Node> map = new HashMap<>();
    DoubleLinked cache = new DoubleLinked();
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            put(key, map.get(key).value);
            return map.get(key).value;
        }
    }

    public void put(int key, int value) {
        Node node = new Node(key, value);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
        } else {
            if (cache.getSize() >= capacity) {
                Node last = cache.removeLast();
                map.remove(last.key);
            }
        }
        cache.addFirst(node);
        map.put(key, node);
    }

}