CodeTop之LRU缓存

题目链接

146. LRU 缓存 - 力扣（LeetCode）

题目解析

算法原理

我们使用双向链表+哈希表的形式来模拟缓存机制

首先我们要自己实现一个双链表, 自己写一个内部类, 这个内部类记录了key,value,prev,next(前驱和后继), 后续我们就通过这个内部类来构造双向链表

其次我们要把LRU缓存机制和我们的双向链表联系起来

我们每次查找一个Key所对应的value, 如果存在的话, 那么就相当于这个key-value组合是常常访问的, 因此我们要把它的优先级提高, 具体的代码就是我们把这个key-value的结点放在双向链表的头部,如果头插后,我们的缓存大小超过了指定大小, 那么就尾删

hash<Integer,DoubleLinkde>, 存key和key-value组成的双链表的结点, DoubleLinkde是我们自定义的内部类来模拟双链表

我们每次查找一个key, 如果在hash表里面能够找到, 那么就把这个结点移动到头部(头插),如果插进去超过大小了, 就尾删, 越靠近后面,访问频次越低.

双链表能够存贮前驱和后继的值, 这样可以很方便进行头插和尾删

代码编写

class LRUCache {private int capacity;// 设置的缓存大小private int currentSize;// 当前缓存的大小private HashMap<Integer, DoubleLinked> map;// 用哈希表存储key-valueprivate DoubleLinked head, tail;// 虚拟头尾结点// 双向链表节点类private class DoubleLinked {int key, value;DoubleLinked prev, next;// 构造方法public DoubleLinked() {}public DoubleLinked(int key, int value) {this.key = key;this.value = value;}}// 构造函数，初始化容量public LRUCache(int capacity) {this.capacity = capacity;this.currentSize = 0;map = new HashMap<>();// 初始化伪头节点和伪尾节点head = new DoubleLinked();tail = new DoubleLinked();head.next = tail;tail.prev = head;}// 获取缓存中的值，如果存在返回值，否则返回-1public int get(int key) {DoubleLinked node = map.get(key);if (node == null) {return -1;}// 访问过该节点，移动到头部moveToHead(node);return node.value;}// 插入一个新的键值对public void put(int key, int value) {DoubleLinked node = map.get(key);if (node == null) {// 插入新节点DoubleLinked newNode = new DoubleLinked(key, value);map.put(key, newNode);addToHead(newNode);currentSize++;if (currentSize > capacity) {// 超过容量，移除尾部节点DoubleLinked tailNode = removeTail();map.remove(tailNode.key);currentSize--;}} else {// 更新已有节点的值，并移动到头部node.value = value;moveToHead(node);}}// 将节点添加到头部private void addToHead(DoubleLinked node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 将节点移到头部private void moveToHead(DoubleLinked node) {if (node == null) {return;}removeNode(node);addToHead(node);}// 移除节点private void removeNode(DoubleLinked node) {if (node == null) {return;}node.prev.next = node.next;node.next.prev = node.prev;}// 移除尾部节点private DoubleLinked removeTail() {if (tail.prev == null) {return null;}DoubleLinked node = tail.prev;removeNode(node);return node;}
}