> ### 数据结构 * 采用 **`HashMap`** 和 **双向链表**的数据结构 * 双向链表中的`Node`保存了缓存的`key`和`value` * `HashMap<key, Node>`，即`value`为双向链表中的节点 * 每访问一个元素将双向链表中的该元素先删除，再添加到头结点，即将最新访问的节点移到头 * 当缓存满，删除链表尾的节点，同时删除map中的key，再将新元素添加到链表头，添加到map * 用双向链表是为了记录尾节点，当缓存满时删除尾节点 * 第一开始想法是用单向链表，再额外记录一下头尾节点，但这样是不行的，单向链表可以记录头结点，没有办法记录尾节点，当一个尾节点被删除后，只能从头遍历到尾才能继续记录尾节点。 <br/> <br/> > ### 如何实现一个高并发下的线程安全的 LRU缓存 ？ <br/> <br/>  <br/>  <br/> <br/> > ### leetcode146 [LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/) ``` class LRUCache { Map<Integer, Node> map = new HashMap<>(); TList list = new TList(); int capacity; static class Node{ int key; int value; Node prev; Node next; public Node(int key, int value){ this.key = key; this.value = value; } } //双向链表，记录头尾节点 static class TList{ Node head; Node tail; //添加节点到链表头 public void add(Node node){ if(head == null){ head = tail = node; node.prev = null; node.next = null; return; } node.next = head; node.prev = null; head.prev = node; head = node; } //移除节点 public void remove(Node node){ if(head.key == tail.key){ head = tail = null; return; } if(node.key == head.key){ head = head.next; head.prev = null; return; } if(node.key == tail.key){ tail = tail.prev; tail.next = null; return; } node.prev.next = node.next; node.next.prev = node.prev; } //移除尾节点 public Node removeTail(){ Node node = tail; if(tail.prev == null){ head = tail = null; return node; } tail.prev.next = null; tail = tail.prev; return node; } } public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { if(map.containsKey(key)){ Node node = map.get(key); list.remove(node); list.add(node); return node.value; }else{ return -1; } } public void put(int key, int value) { Node node = new Node(key, value); //put key已存在 if(map.containsKey(key)){ Node old = map.get(key); old.value = value; list.remove(old); list.add(old); return; } //判断是否超过容量 if(map.size() == capacity){ node = list.removeTail(); map.remove(node.key); Node newNode = new Node(key, value); map.put(key, newNode); list.add(newNode); }else{ map.put(key, node); list.add(node); } } } ``` *** 参考： [LRU原理和Redis实现](https://zhuanlan.zhihu.com/p/34133067)