一、設計思路

1。 資料儲存

資料儲存使用開放地址雜湊表，而不是使用連結串列雜湊的方式

，從而保證存放最多指定容量的資料。如果發生衝突，則往下查詢直到找到一個空位置。

對應的資料結構層面，則是使用陣列，更確切地說是環形陣列，因為當發生衝突時，需要查詢除了直接透過 key % 容量capacity 取模之外的所有其他位置一遍，直到找到一個可以存放該鍵值對的位置。對於資料獲取，也是類似的思路。

2。 LRU特性實現

仿照Java的linkedhashmap來維護一個雙向連結串列，每次訪問一個節點或者新增一個節點則放到連結串列尾部，刪除節點，則刪除連結串列首部節點，實現O（1）複雜度。

二、編碼實現

leetcode已透過： LRU快取

class LRUCache { // 解題思路： // 仿照Java的linkedhashmap來維護一個雙向連結串列，每次訪問一個節點或者新增一個節點則放到連結串列尾部 // 刪除節點，則刪除連結串列首部節點 // 資料儲存使用開放地址雜湊表，就衝突節點放在下一個空位置，而不是使用連結串列雜湊的方式 private Node head； private Node tail； private int capacity； private int size； private Node［］ table； public LRUCache（int capacity） { if （capacity > 0） { this。capacity = capacity； this。table = new Node［capacity］； } } public int get（int key） { if （capacity <= 0 || key < 0 || size == 0） { return -1； } // 目標位置 int arrayIndex = key % capacity； Node target = table［arrayIndex］； // 存在衝突不在目標位置 if （target == null || target。key ！= key） { int nextLocation = （arrayIndex + 1） % capacity； while （nextLocation ！= arrayIndex） { Node node = table［nextLocation］； if （node ！= null && node。key == key） { // 找到 target = node； break； } else { nextLocation = （nextLocation + 1） % capacity； } } } if （target ！= null && target。key == key） { // 維護雙向連結串列，放到連結串列尾部 adjustNodeAccessLocation（target）； return target。value； } else { // 未找到 return -1； } } public void put（int key， int value） { if （capacity <= 0 || key < 0） { return； } Node target = null； // 查詢當前節點是否存在，存在則更新，否則插入 for （int i = 0； i < table。length； i++） { Node node = table［i］； if （node ！= null && node。key == key） { target = node； break； } } if （target ！= null） { // 更新 target。value = value； adjustNodeAccessLocation（target）； } else { // 新增 // 容量滿了，刪除最近最少訪問的元素，即head節點 if （size == capacity） { Node toDeletedNode = head； head = head。next； if （head == null） { tail = null； } else { head。pre = null； } table［toDeletedNode。arrayIndex］ = null； toDeletedNode = null； size——； } // 取模獲取陣列下標，如果已經存在元素，則往下查詢直到查詢到一個空閒位置， // 注意是環形陣列，直到當前陣列下標的前一個位置 int arrayIndex = key % capacity； Node node = table［arrayIndex］； Node newNode = new Node（key， value）； if （node == null） { newNode。arrayIndex = arrayIndex； table［arrayIndex］ = newNode； } else { // 存在衝突，遍歷直到找到一個空位置，環形陣列故與capacity取模，避免越界問題 int nextLocation = （arrayIndex + 1） % capacity； // 查詢直到回到原位置 while （nextLocation ！= arrayIndex） { if （table［nextLocation］ == null） { // 找到 newNode。arrayIndex = nextLocation； table［nextLocation］ = newNode； break； } else { // 往下查詢 nextLocation = （nextLocation + 1） % capacity； } } } size++； target = newNode； // 新節點追加到雙向連結串列尾部 addNewNodeToTail（target）； } } private void adjustNodeAccessLocation（Node target） { // 存在兩個以上節點且不是訪問尾結點 if （head ！= tail && target ！= tail） { // 訪問頭結點 if （head == target） { head = head。next； head。pre = null； tail。next = target； target。pre = tail； tail = target； } else { // 訪問中間節點 // 調整當前節點的雙向連結串列的前後節點 target。pre。next = target。next； target。next。pre = target。pre； // 當前節點放到連結串列尾部 tail。next = target； target。pre = tail； tail = target； } } } private void addNewNodeToTail（Node target） { if （head == null && tail == null） { head = tail = target； } else { tail。next = target； target。pre = tail； tail = target； } } private class Node { public int key； public int value； // 最佳化效能：當前在雜湊表陣列的下標，O（1）時間複雜度刪除 public int arrayIndex； public Node pre； public Node next； public Node（） {} public Node（int key， int value） { this。key = key； this。value = value； this。pre = null； this。next = null； } }}/** * Your LRUCache object will be instantiated and called as such： * LRUCache obj = new LRUCache（capacity）； * int param_1 = obj。get（key）； * obj。put（key，value）； */```