LRU缓存结构
问题描述：
设计可以变更的缓存结构（LRU）
【题目】
设计一种缓存结构，该结构在构造时确定大小，假设大小为K，并有两个功能：
set(key,value)：将记录(key,value)插入该结构。
get(key)：返回key对应的value值。
【要求】
1．set和get方法的时间复杂度为O(1)。
2．某个key的set或get操作一旦发生，认为这个key的记录成了最经常使用的。
3．当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
【举例】
假设缓存结构的实例是cache，大小为3，并依次发生如下行为：
1．cache.set("A",1)。最经常使用的记录为("A",1)。
2．cache.set("B",2)。最经常使用的记录为("B",2)，("A",1)变为最不经常的。
3．cache.set("C",3)。最经常使用的记录为("C",2)，("A",1)还是最不经常的。
4．cache.get("A")。最经常使用的记录为("A",1)，("B",2)变为最不经常的。
5．cache.set("D",4)。大小超过了3，所以移除此时最不经常使用的记录("B",2)，
加入记录 ("D",4)，并且为最经常使用的记录，然后("C",2)变为最不经常使用的
记录
分析问题
- 简单分析LRU结构需要以下几个功能
- 必须有明确的大小K，可在构造方法中传入
- set方法为键值对的形式，所以必须准备HasnMap，才能使得set和get方法的时间复杂度为O(1);
- 调整某个key成为最经常用的节点，所以可以维护一个关于value的双向链表，那么这里直接做一个Node节点，value作为他的属性之一。
- 当大小超载时，移除最不经常使用的，假设双端链表尾部就是最经常使用的节点，双端链表头部最不进场使用，所以这里直接把头节点删掉就可以了
- 一旦对一个节点进行修改了，那么需要将修改的节点移动到双端聊表尾部。
代码
static class Node<V>{
V value;
Node<V> last;
Node<V> next;
public Node(V value) {
this.value = value;
}
}
static class DoubleLinkedList<V>{
Node<V> head;
Node<V> tail;
public DoubleLinkedList(){
this.head = null;
this.tail = null;
}
// 添加一个节点
void addNode(Node node){
if(head == null){
this.head = node;
this.tail = node;
}else{
this.tail.next = node;
node.last = this.tail;
this.tail = node;
}
}
// 将某个节点node移动到链表尾部
void moveNodeToTail(Node node){
if(this.tail == node){
return;
}
if(this.head == node){
this.head = node.next;
this.head.last = null;
}else{
node.last.next = node.next;
node.next.last = node.last;
}
node.last = this.tail;
node.next = null;
this.tail.next = node;
this.tail = node;
}
// 移除双向链表的头节点
Node<V> removeHeadNode(){
if(this.head == null) {
return null;
}
Node<V> res = this.head;
if(this.head == this.tail){
this.head = null;
this.tail = null;
}else{
this.head = res.next;
res.next = null;
this.head.last = null;
}
return res;
}
}
public static class MyCache<K,V>{
HashMap<K,Node<V>> keyNodeMap;
HashMap<Node<V>,K> valueKeyMap;
DoubleLinkedList<V> nodeList;
int capacity;
public MyCache(int capacity) {
if(capacity < 1){
throw new RuntimeException("容量不可以小于1");
}
this.capacity = capacity;
this.keyNodeMap = new HashMap<>();
this.valueKeyMap = new HashMap<>();
this.nodeList = new DoubleLinkedList<>();
}
// 根据指定的K获取value
public V get(K key){
if(this.keyNodeMap.containsKey(key)){
Node<V> res = this.keyNodeMap.get(key);
this.nodeList.moveNodeToTail(res);
return res.value;
}
return null;
}
// 向缓存结构中添加键值对
public void set(K key,V value){
if(this.keyNodeMap.containsKey(key)){
Node<V> cur = this.keyNodeMap.get(key);
cur.value = value;
this.nodeList.moveNodeToTail(cur);
}else{
Node<V> temp = new Node<V>(value);
this.keyNodeMap.put(key,temp);
this.valueKeyMap.put(temp,key);
this.nodeList.addNode(temp);
if(this.keyNodeMap.size() == this.capacity + 1){
Node<V> removeValue = this.nodeList.removeHeadNode();
K removeKey = this.valueKeyMap.get(removeValue);
this.keyNodeMap.remove(removeKey);
this.valueKeyMap.remove(removeValue);
}
}
}
}
LFU缓存结构
题目描述
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
- get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
- put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
【项的使用次数】就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
基本思路
- 同LRU结构，将键值对存储在Node节点中。
- 创建一个双向链表，链表中每一个位置都是一个双向链表，所有具有相同操作次数的节点node放在同一个位置重新构成双向链表
- 所以当插入一个元素时，如果该元素存在，则需要将其操作次数加1，然后将其添加到大链表的新的位置中；如果不存在，则创建该节点，默认操作次数为1
- 获取一个元素时，该Node的操作次数也加1，然后调整到大链表新的位置
- 剩下的问题就是扣边界了。
代码
// 首先定义节点类型
class Node{
int key;
int value;
int times;
Node up;
Node down;
public Node(int key, int value, int times){
this.key = key;
this.value = value;
this.times = times;
}
}
//定义NodeList类，LFU包含一个由NodeList构成的双端链表
class NodeList{
Node head;
Node tail;
NodeList last;
NodeList next;
public NodeList(Node node){
this.head = node;
this.tail = node;
}
// 将一个节点node插入此nodeList的头步
public void addNodeFromHead(Node newNode){
newNode.down = this.head;
this.head.up = newNode;
this.head = newNode;
}
// 判断当前的nodeList是否为null
public boolean isEmpty(){
return this.head == null;
}
// 从当前的nodeList中删除一个node
public void deleteNode(Node node){
if(this.head == this.tail){
this.head = null;
this.tail = null;
}else{
if(this.head == node){
this.head = node.down;
this.head.up = null;
}else if(this.tail == node){
this.tail = node.up;
this.tail.down = null;
}else{
node.up.down = node.down;
node.down.up = node.up;
}
}
node.up = null;
node.down = null;
}
}
class LFUCache {
// 定义成员变量
int capacity;
int size;
HashMap<Integer,Node> records;
HashMap<Node,NodeList> heads;
NodeList headList;
public LFUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
this.records = new HashMap<Integer,Node>();
this.heads = new HashMap<Node,NodeList>();
this.headList = null;
}
public int get(int key) {
int res = -1;
if(records.containsKey(key)){
Node node = records.get(key);
res = node.value;
node.times++;
NodeList curNodeList = heads.get(node);
move(node,curNodeList);
}
return res;
}
public void put(int key, int value) {
if(this.capacity == 0) {
return;
}
// 如果当前的key指向的节点存在
if(records.containsKey(key)){
Node node = records.get(key);
node.value = value;
node.times++;
NodeList curNodeList = heads.get(node); // 获取当前的node存在的NodeList
move(node,curNodeList); // 将node移动到新的NodeList中，并调正curNodeList
}
// 如果当前的key指向的节点不存在
else{
//r如果容量超限
if(this.size == this.capacity){
//删除headList的tail
Node tail = this.headList.tail;
this.headList.deleteNode(tail);
modifyHeadList(this.headList); // 更新当前的headList，如果为null调整
records.remove(tail.key);
heads.remove(tail);
this.size--;
}
// 创建新的Node进行插入
Node node = new Node(key,value,1);
if(this.headList == null){
this.headList = new NodeList(node);
}else{
if(this.headList.head.times == node.times){
this.headList.addNodeFromHead(node);
}else{
NodeList newList = new NodeList(node);
newList.next = this.headList;
this.headList.last = newList;
this.headList = newList;
}
}
records.put(key,node);
heads.put(node,this.headList);
this.size++;
}
}
private void move(Node node, NodeList oldNodeList){
// 首先从原来的NodeList中删除node节点
oldNodeList.deleteNode(node);
NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList; // 调整oldNodeList
NodeList nextList = oldNodeList.next;
if(nextList == null){
// 新建一个Nodelist,把node扔进去
NodeList newList = new NodeList(node);
if(preList != null){
preList.next = newList;
}
newList.last = preList;
if(this.headList == null){
this.headList = newList;
}
heads.put(node,newList);
}else{
if(nextList.head.times == node.times){
// 将node放到头步
nextList.addNodeFromHead(node);
heads.put(node,nextList);
}else{
NodeList newList = new NodeList(node);
if(preList != null){
preList.next = newList;
}
newList.last = preList;
newList.next = nextList;
nextList.last = newList;
if(this.headList == nextList){
this.headList = newList;
}
heads.put(node,newList);
}
}
}
private boolean modifyHeadList(NodeList nodeList){
// 如果当前的nodeList为null，则要进行删除
if(nodeList.isEmpty()){
if(this.headList == nodeList){
this.headList = nodeList.next;
if(this.headList != null){
this.headList.last = null;
}
}else{
nodeList.last.next = nodeList.next;
if(nodeList.next != null){
nodeList.next.last = nodeList.last;
}
}
return true;
}
//否则返回false
return false;
}
}
