> ### 數據結構 * 采用 **`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)