LRU实现基于map和双向链表实现

tail.next=node;
node.prev=tail;
node.next=null;
tail=node;

node.prev.next=node.next;
node.next.prev=node.prev;

publicLRUCache<K,V>{
privateintmaxCapacity; // 最大容量privateMap<K,Node<K,V>>map; // 缓存数据结构主体privateNode<K,V>prev,tail; // 存储数据双向链表，保证有序//节点域publicNode(Kkey, Vvalue) {
this.key=key;
this.value=value;
    }
}

1.首先考虑key是否存在，如果存在，则进行remove，然后执行放入操作put。2.否则，考虑容量是否充足，如果不够，则进行缓存过期操作。也即将队头的数据进行删除操作，然后执行存放数据操作。3.如果缓存容量够，则直接执行放入指针指向。

//放入缓存操作publicvoidput(Kkey, Vvalue) {
//判断map中是否包含key,如果包含，则需要执行更新操作，首先进行删除，然后执行更新if (map.containsKey(key)) {
Node<K, V>node=map.get(key);
node.value=value;
removeNode(node);
offerNode(node);
    } else {
//否者，首先考虑map容量是否充足，如果不充足，则考虑进行过期操作，// 也即进行删除操作，然后放入节点数据信息，然后放入到map中if (map.size() ==maxCapacity) {
map.remove(head.key);
removeNode(head);
        }
Node<K, V>node=newNode<>(key, value);
offerNode(node);
map.put(key, node);
    }
}

//获取缓存数据publicVget(Kkey) {
Node<K, V>node=map.get(key);
//先判空，然后执行删除操作，执行放入操作if (node==null) returnnull;
removeNode(node);
offerNode(node);
returnnode.value;
}

1.如果当前节点为空，则直接返回，说明没有元素可添加2.如果当前节点头节点为空，说明插入的元素是第一个，此时head=tail=node3.否者，说明在插入当前节点元素的前就有元素了，因此此时考虑进行节点插入指向关系的考虑：因为有序，所以考虑尾插：tail.next=node;
node.prev=tail;
node.next=null;
tail=node;

1.判断当前节点是否为空，如果为空，则直接返回，说明没有元素需要删除2.考虑当前节点的前驱节点不为空的情况，此时需要进行当前节点的前驱节点的后继节点指向当前节点的下一个节点，否则前驱节点为空，说明当前节点为头结点，此时将头结点指向下一个节点3.考虑当前节点的后继节点不为空的情况，此时需要将当前节点的下一节点的前驱节点指向当前节点的前驱节点，否者说明后继节点为空，则说明当前节点就是tail节点，此时需要将tail节点指向当前节点的前驱节点

publicLruCacheV3(finalintmaxCapacity) {
intcores=Runtime.getRuntime().availableProcessors();
intconcurrency=cores<2?2 : cores;
cacheSegments=newLruCacheV2[concurrency];
intsegmentCapacity=maxCapacity/concurrency;
if (maxCapacity%concurrency==1) segmentCapacity++;
for (intindex=0; index<cacheSegments.length; index++) {
cacheSegments[index] =newLruCacheV2<>(segmentCapacity);
    }
}