import java.util.HashMap; import java.util.Map; /** * @since 2020/9/26 9:20 */ public class LRUCache<K, V> { static class Node<K, V> { K key; V value; Node<K, V> pre; Node<K, V> next; public Node() { } public Node(K key, V value) { this.key = key; this.value = value; } } private int size; private int capacity; private Node<K, V> head; private Node<K, V> tail; private final Map<K, Node<K, V>> cache = new HashMap<>(); public LRUCache() { this(10); } public LRUCache(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("capacity <= 0"); } this.size = 0; this.capacity = capacity; this.head = new Node<>(); this.tail = new Node<>(); head.next = tail; tail.pre = head; } public V get(K key) { if (key == null) { throw new NullPointerException("key == null"); } Node<K, V> node = cache.get(key); if (node == null) { return null; } moveToHead(node); return node.value; } public void put(K key, V value) { if (key == null || value == null) { throw new NullPointerException("key == null || value == null"); } Node<K, V> node = cache.get(key); if (node == null) { Node<K, V> newNode = new Node<>(key, value); cache.put(key, newNode); addToHead(newNode); ++size; if (size > capacity) { Node<K, V> tail = removeTail(); cache.remove(tail.key); --size; } } else { node.value = value; moveToHead(node); } } private void moveToHead(Node<K, V> node) { removeNode(node); addToHead(node); } private void addToHead(Node<K, V> node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } private void removeNode(Node<K, V> node) { node.pre.next = node.next; node.next.pre = node.pre; } private Node<K, V> removeTail() { Node<K, V> node = tail.pre; removeNode(node); return node; } }