LRU实现基于map和双向链表实现
前面我们已经看到了单链表的数据结构：数据域和节点域node。而双向链表则是：数据域和节点域（包含前驱节点和后继节点）。
单链表
双向链表
如果我们想完成一个简单的LRU的缓存，可以考虑基于双向链表和map实现。思路：
可以基于map的数据结构，value基于双向链表，也即有前驱节点和后继节点。而此时删除和添加操作时，其实实质是考虑双向链表的添加和删除操作。因此我们来看一下双向链表的添加和删除操作：
双向链表插入节点数据
、
此时插入关系：
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
双向链表删除节点数据
此时需要考虑前驱节点和后继节点
node.prev.next = node.next;
node.next.prev = node.prev;
因此基于此我们的LRU缓存的数据结构是：
public LRUCache<K,V>{
private int maxCapacity; // 最大容量
private Map<K,Node<K,V>> map; // 缓存数据结构主体
private Node<K,V> prev,tail; // 存储数据双向链表，保证有序
//节点域
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
此时考虑执行存放数据时，使用的是map的数据结构，因此需要考虑put的时候
1.首先考虑key是否存在，如果存在，则进行remove，然后执行放入操作put。
2.否则，考虑容量是否充足，如果不够，则进行缓存过期操作。也即将队头的数据进行删除操作，然后执行存放数据操作。
3.如果缓存容量够，则直接执行放入指针指向。
放入操作的实现
//放入缓存操作
public void put(K key, V value) {
//判断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 = new Node<>(key, value);
offerNode(node);
map.put(key, node);
}
}
元素获取操作
//获取缓存数据
public V get(K key) {
Node<K, V> node = map.get(key);
//先判空，然后执行删除操作，执行放入操作
if (node == null) return null;
removeNode(node);
offerNode(node);
return node.value;
}
而删除和添加元素的过程在上面的图中已经有提及，这里分析过程：
添加元素
1.如果当前节点为空，则直接返回，说明没有元素可添加
2.如果当前节点头节点为空，说明插入的元素是第一个，此时head=tail=node
3.否者，说明在插入当前节点元素的前就有元素了，因此此时考虑进行节点插入指向关系的考虑：
因为有序，所以考虑尾插：
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
元素删除操作
1.判断当前节点是否为空，如果为空，则直接返回，说明没有元素需要删除
2.考虑当前节点的前驱节点不为空的情况，此时需要进行当前节点的前驱节点的后继节点指向当前节点的下一个节点，否则前驱节点为空，说明当前节点为头结点，此时将头结点指向下一个节点
3.考虑当前节点的后继节点不为空的情况，此时需要将当前节点的下一节点的前驱节点指向当前节点的前驱节点，否者说明后继节点为空，则说明当前节点就是tail节点，此时需要将tail节点指向当前节点的前驱节点
但是此时我们看到的LRU程序是线程不安全的，同时如果想要在并发场景下使用，需要考虑线程安全的问题，因此此时我们考虑读写锁对其进行优化，同时考虑锁的粒度的细化。此时的读写锁放在map的get和put操作中。
但是如果想要性能也变得相对高一些，那还需要进行优化，此时我们考虑对锁进一步进行细化，同时利用cpu的多核处理器，也即采用分段锁的方式对锁进行细化。此时对对象进行锁的细化。
public LruCacheV3(final int maxCapacity) {
int cores = Runtime.getRuntime().availableProcessors();
int concurrency = cores < 2 ? 2 : cores;
cacheSegments = new LruCacheV2[concurrency];
int segmentCapacity = maxCapacity / concurrency;
if (maxCapacity % concurrency == 1) segmentCapacity++;
for (int index = 0; index < cacheSegments.length; index++) {
cacheSegments[index] = new LruCacheV2<>(segmentCapacity);
}
}
此时对缓存对象进行细化。
如果我们遇到的缓存比较大时，此时又需要考虑怎样的缓存设计呢？
此时由于缓存的消息或者信息比较大时，同时呈现成批量时，可以基于消息，考虑使用文件存储的方式进行，此时可以考虑NIO的处理方式，使用FileChannel和MappedByteBuffer或者堆外内存的方式，此时基于块状消息处理，使用缓冲区或者使用通道。此时的处理不经过用户态，因此性能上也是比较高的。
当然基于LinkedHashMap也可以实现LRU缓存设计。LinkedHashMap本身就是基于HashMap+双向链表实现的。
代码实现参考波波老师讲的分布式系统设计。