146. LRU 缓存

---

前言

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

实现的方法
0)构造方法, cache大小

1. void put(key, value)
2. void update(key, value)
3. V get(key)
   要求时间复杂度0(1),就规避掉了遍历O(N),以及有序表O(N*logN)

数据结构的设计题别慌，它一定都是简单数据结构就能够实现的，
就是看这种简单的数据结构怎么组合而已，包括很难的LRU, LFU都一样.

双向链表+哈希表实现
Hash表里 A
value: Key对应的节点Node (A, 3),
一个双向链表的节点有last, next指针
用双向链表来表示谁是较近操作的,谁是较远操作的
越靠近双向链表的尾巴越近，越靠近双向链表的头部越远
双向链表记一个头指针，记一个尾指针,可以很方便的把一个数据直接挂在尾巴上。

手动实现双向链表.
1)新加一个Node节点,挂在双向链表尾部
2)已知一个Node一定在双向链表上,把Node前后环境重新连接后把它挂在尾巴上
3)在双向链表中删除头节点

代码

class LRUCache {
    
    private MyCache<Integer,Integer> cache;
    public LRUCache(int capacity) {
    
		cache = new MyCache<>(capacity);
	}

	public int get(int key) {
    
		Integer ans = cache.get(key);
		return ans == null ? -1 : ans;
	}

	public void put(int key, int value) {
    
		cache.set(key, value);
	}

	public static class Node<K, V> {
    
		public K key;
		public V value;
		public Node<K, V> last;
		public Node<K, V> next;

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

	public static class NodeDoubleLinkedList<K, V> {
    
		private Node<K, V> head;
		private Node<K, V> tail;

		public NodeDoubleLinkedList() {
    
			head = null;
			tail = null;
		}

		public void addNode(Node<K, V> newNode) {
    
			if (newNode == null) {
    
				return;
			}
			if (head == null) {
    
				head = newNode;
				tail = newNode;
			} else {
    
				tail.next = newNode;
				newNode.last = tail;
				tail = newNode;
			}
		}

		public void moveNodeToTail(Node<K, V> node) {
    
			if (tail == node) {
    
				return;
			}
			// node 不是尾巴
			if (head == node) {
    
				head = node.next;
				head.last = null;
			} else {
    
				node.last.next = node.next;
				node.next.last = node.last;
			}
			node.last = tail;
			node.next = null;
			tail.next = node;
			tail = node;
		}

		public Node<K, V> removeHead() {
    
			if (head == null) {
    
				return null;
			}
			Node<K, V> res = head;
			if (head == tail) {
     // 链表中只有一个节点的时候
				head = null;
				tail = null;
			} else {
    
				head = res.next;
				res.next = null;
				head.last = null;
			}
			return res;
		}

	}

	public static class MyCache<K, V> {
    
		private HashMap<K, Node<K, V>> keyNodeMap;
		private NodeDoubleLinkedList<K, V> nodeList;
		private final int capacity;

		public MyCache(int cap) {
    
			if (cap < 1) {
    
				throw new RuntimeException("should be more than 0.");
			}
			keyNodeMap = new HashMap<K, Node<K, V>>();
			nodeList = new NodeDoubleLinkedList<K, V>();
			capacity = cap;
		}

		public V get(K key) {
    
			if (keyNodeMap.containsKey(key)) {
    
				Node<K, V> res = keyNodeMap.get(key);
				nodeList.moveNodeToTail(res);
				return res.value;
			}
			return null;
		}

		public void set(K key, V value) {
    
			if (keyNodeMap.containsKey(key)) {
    
				Node<K, V> node = keyNodeMap.get(key);
				node.value = value;
				nodeList.moveNodeToTail(node);
			} else {
    
				if (keyNodeMap.size() == capacity) {
    
					removeMostUnusedCache();
				}
				Node<K, V> newNode = new Node<K, V>(key, value);
				keyNodeMap.put(key, newNode);
				nodeList.addNode(newNode);
			}
		}

		private void removeMostUnusedCache() {
    
			Node<K, V> removeNode = nodeList.removeHead();
			keyNodeMap.remove(removeNode.key);
		}

	}
}