題目鏈接

146. LRU 緩存 - 力扣（LeetCode）

題目解析

算法原理

我們使用雙向鏈表+哈希表的形式來模擬緩存機制

首先我們要自己實現一個雙鏈表, 自己寫一個內部類, 這個內部類記錄了key,value,prev,next(前驅和后繼), 后續我們就通過這個內部類來構造雙向鏈表

其次我們要把LRU緩存機制和我們的雙向鏈表聯系起來

我們每次查找一個Key所對應的value, 如果存在的話, 那么就相當于這個key-value組合是常常訪問的, 因此我們要把它的優先級提高, 具體的代碼就是我們把這個key-value的結點放在雙向鏈表的頭部,如果頭插后,我們的緩存大小超過了指定大小, 那么就尾刪

hash<Integer,DoubleLinkde>, 存key和key-value組成的雙鏈表的結點,?DoubleLinkde是我們自定義的內部類來模擬雙鏈表

我們每次查找一個key, 如果在hash表里面能夠找到, 那么就把這個結點移動到頭部(頭插),如果插進去超過大小了, 就尾刪, 越靠近后面,訪問頻次越低.

雙鏈表能夠存貯前驅和后繼的值, 這樣可以很方便進行頭插和尾刪

代碼編寫

class LRUCache {private int capacity;// 設置的緩存大小private int currentSize;// 當前緩存的大小private HashMap<Integer, DoubleLinked> map;// 用哈希表存儲key-valueprivate DoubleLinked head, tail;// 虛擬頭尾結點// 雙向鏈表節點類private class DoubleLinked {int key, value;DoubleLinked prev, next;// 構造方法public DoubleLinked() {}public DoubleLinked(int key, int value) {this.key = key;this.value = value;}}// 構造函數，初始化容量public LRUCache(int capacity) {this.capacity = capacity;this.currentSize = 0;map = new HashMap<>();// 初始化偽頭節點和偽尾節點head = new DoubleLinked();tail = new DoubleLinked();head.next = tail;tail.prev = head;}// 獲取緩存中的值，如果存在返回值，否則返回-1public int get(int key) {DoubleLinked node = map.get(key);if (node == null) {return -1;}// 訪問過該節點，移動到頭部moveToHead(node);return node.value;}// 插入一個新的鍵值對public void put(int key, int value) {DoubleLinked node = map.get(key);if (node == null) {// 插入新節點DoubleLinked newNode = new DoubleLinked(key, value);map.put(key, newNode);addToHead(newNode);currentSize++;if (currentSize > capacity) {// 超過容量，移除尾部節點DoubleLinked tailNode = removeTail();map.remove(tailNode.key);currentSize--;}} else {// 更新已有節點的值，并移動到頭部node.value = value;moveToHead(node);}}// 將節點添加到頭部private void addToHead(DoubleLinked node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 將節點移到頭部private void moveToHead(DoubleLinked node) {if (node == null) {return;}removeNode(node);addToHead(node);}// 移除節點private void removeNode(DoubleLinked node) {if (node == null) {return;}node.prev.next = node.next;node.next.prev = node.prev;}// 移除尾部節點private DoubleLinked removeTail() {if (tail.prev == null) {return null;}DoubleLinked node = tail.prev;removeNode(node);return node;}
}