LRU缓存结构
方法：哈希表+双向链表
知识点1：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)O(1)O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。
知识点2：双向链表
双向链表是一种特殊的链表，它除了链表具有的每个节点指向后一个节点的指针外，还拥有一个每个节点指向前一个节点的指针，因此它可以任意向前或者向后访问，每次更改节点连接状态的时候，需要变动两个指针。
思路：
插入与访问值都是O(1)O(1)O(1)，没有任何一种数据结构可以直接做到。
于是我们可以想到数据结构的组合：访问O(1)O(1)O(1)很容易想到了哈希表；插入O(1)O(1)O(1)的数据结构有很多，但是如果访问到了这个地方再选择插入，且超出长度要在O(1)O(1)O(1)之内删除，我们可以想到用链表，可以用哈希表的key值对应链表的节点，完成直接访问。但是我们还需要把每次访问的key值节点加入链表头，同时删掉链表尾，所以选择双向链表，便于删除与移动。
于是我们的方法就是哈希表+双向链表。
具体做法：
- step 1：构建一个双向链表的类，记录key值与val值，同时一前一后两个指针。用哈希表存储key值和链表节点，这样我们可以根据key值在哈希表中直接锁定链表节点，从而实现在链表中直接访问，能够做到O(1)O(1)O(1)时间访问链表任意节点。
//设置双向链表结构
class Node{
int key;
int val;
Node pre;
Node next;
//初始化
public Node(int key, int val) {
this.key = key;
this.val = val;
this.pre = null;
this.next = null;
}
}
- step 2：设置全局变量，记录双向链表的头、尾及LRU剩余的大小，并全部初始化，首尾相互连接好。
//构建初始化连接
//链表剩余大小
this.size = k;
this.head.next = this.tail;
this.tail.pre = this.head;
- step 3：遍历函数的操作数组，检查第一个元素判断是属于set操作还是get操作。
- step 4：如果是set操作，即将key值与val值加入链表，我们先检查链表中是否有这个key值，可以通过哈希表检查出，如果有直接通过哈希表访问链表的相应节点，修改val值，并将访问过的节点移到表头；如果没有则需要新建节点加到表头，同时哈希表中增加相应key值（当然，还需要检查链表长度还有无剩余，若是没有剩余则需要删去链表尾）。
//没有见过这个key，新值加入
if(!mp.containsKey(key)){
Node node = new Node(key, val);
mp.put(key, node);
//超出大小，移除最后一个
if(size <= 0)
removeLast();
//大小还有剩余
else
//大小减1
size--;
//加到链表头
insertFirst(node);
}
//哈希表中已经有了，即链表里也已经有了
else{
mp.get(key).val = val;
//访问过后，移到表头
moveToHead(mp.get(key));
}
- step 5：不管是新节点，还是访问过的节点都需要加到表头，若是访问过的，需要断开原来的连接，再插入表头head的后面。
//移到表头函数
void moveToHead(Node node){
//已经到了表头
if(node.pre == head)
return;
//将节点断开，取出来
node.pre.next = node.next;
node.next.pre = node.pre;
//插入第一个前面
insertFirst(node);
}
- step 6：删除链表尾需要断掉尾节点前的连接，同时哈希表中去掉这个key值。
void removeLast(){
//哈希表去掉key
mp.remove(tail.pre.key);
//断连该节点
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
}
- step 7：如果是get操作，检验哈希表中有无这个key值，如果没有说明链表中也没有，返回-1，否则可以根据哈希表直接锁定链表中的位置进行访问，然后重复step 5，访问过的节点加入表头。
if(mp.containsKey(key)){
Node node = mp.get(key);
res = node.val;
moveToHead(node);
}
图示：
Java代码实现:
import java.util.*;
public class Solution {
//设置双向链表结构
static class Node{
int key;
int val;
Node pre;
Node next;
//初始化
public Node(int key, int val) {
this.key = key;
this.val = val;
this.pre = null;
this.next = null;
}
}
//哈希表
private Map<Integer, Node> mp = new HashMap<>();
//设置一个头
private Node head = new Node(-1, -1);
//设置一个尾
private Node tail = new Node(-1, -1);
private int size = 0;
public int[] LRU (int[][] operators, int k) {
//构建初始化连接
//链表剩余大小
this.size = k;
this.head.next = this.tail;
this.tail.pre = this.head;
//获取操作数
int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
int[] res = new int[len];
//遍历所有操作
for(int i = 0, j = 0; i < operators.length; i++){
if(operators[i][0] == 1)
//set操作
set(operators[i][1], operators[i][2]);
else
//get操作
res[j++] = get(operators[i][1]);
}
return res;
}
//插入函数
private void set(int key, int val){
//没有见过这个key，新值加入
if(!mp.containsKey(key)){
Node node = new Node(key, val);
mp.put(key, node);
//超出大小，移除最后一个
if(size <= 0)
removeLast();
//大小还有剩余
else
//大小减1
size--;
//加到链表头
insertFirst(node);
}
//哈希表中已经有了，即链表里也已经有了
else{
mp.get(key).val = val;
//访问过后，移到表头
moveToHead(mp.get(key));
}
}
//获取数据函数
private int get(int key){
int res = -1;
if(mp.containsKey(key)){
Node node = mp.get(key);
res = node.val;
moveToHead(node);
}
return res;
}
//移到表头函数
private void moveToHead(Node node){
//已经到了表头
if(node.pre == head)
return;
//将节点断开，取出来
node.pre.next = node.next;
node.next.pre = node.pre;
//插入第一个前面
insertFirst(node);
}
//将节点插入表头函数
private void insertFirst(Node node){
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
//删去表尾函数，最近最少使用
private void removeLast(){
//哈希表去掉key
mp.remove(tail.pre.key);
//断连该节点
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
}
}
OPPO公司氛围 127人发布