面試高頻考題——手?jǐn)]一個(gè) LRU 算法！
今天給大家講一道面試中經(jīng)常容易遇到的一道題：“手寫(xiě)一個(gè) LRU 算法”。
LRU 就是 Least Recently Used 的縮寫(xiě)，翻譯過(guò)來(lái)就是“最近最少使用”。 也就是說(shuō) LRU 算法會(huì)將最近最少用的緩存移除，讓給最新使用的緩存。這是非常常見(jiàn)的一個(gè)緩存淘汰策略。
利用好 LRU 算法，我們能夠提高對(duì)熱點(diǎn)數(shù)據(jù)的緩存效率，進(jìn)而提升緩存服務(wù)的內(nèi)存使用率。
那么如何實(shí)現(xiàn)呢？
其實(shí)，通過(guò)緩存的 key 獲取其對(duì)應(yīng)的緩存，我們應(yīng)該能想到用哈希表來(lái)實(shí)現(xiàn)，畢竟這是一個(gè)鍵值對(duì)結(jié)構(gòu)，可以在 O(1) 時(shí)間內(nèi)獲取 key 對(duì)應(yīng)的緩存值。
但是，哈希表本身是無(wú)序的，因此，我們還需要一個(gè)類(lèi)似于隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄訪問(wèn)的先后順序，將最近訪問(wèn)的數(shù)據(jù)放在頭部（如下圖），移除最后一項(xiàng)數(shù)據(jù)（最舊），我們可以用雙向鏈表來(lái)實(shí)現(xiàn)數(shù)據(jù)的增刪以及順序的調(diào)整。
因此，我們結(jié)合“哈希表 + 雙向鏈表”來(lái)實(shí)現(xiàn) LRU 算法。其中：
?雙向鏈表按照被使用的順序存儲(chǔ) kv 鍵值對(duì)，靠近頭部的 kv 鍵值對(duì)是最近使用的，而靠近尾部的鍵值對(duì)是最久未使用的。?哈希表通過(guò)緩存的 key 映射到雙向鏈表中的位置。我們可以在 O(1) 時(shí)間內(nèi)定位到緩存的 key 所對(duì)應(yīng)的 value 在鏈表中的位置。
對(duì)于 get 操作，判斷 key 是否存在哈希表中：
?若不存在，返回 -1。?若存在，則 key 對(duì)應(yīng)的節(jié)點(diǎn) node 是最近使用的節(jié)點(diǎn)。將該節(jié)點(diǎn)移動(dòng)到雙向鏈表的頭部，最后返回該節(jié)點(diǎn)的值即可。
對(duì)于 put 操作，同樣先判斷 key 是否存在哈希表中：
?若不存在，則創(chuàng)建一個(gè)新的 node 節(jié)點(diǎn)，放入哈希表中。然后在雙向鏈表的頭部添加該節(jié)點(diǎn)。接著判斷雙向鏈表節(jié)點(diǎn)數(shù)是否超過(guò) capacity。若超過(guò)，則刪除雙向鏈表的尾部節(jié)點(diǎn)，并且刪除哈希表中對(duì)應(yīng)的項(xiàng)。?若存在，則更新 node 節(jié)點(diǎn)的值，然后該節(jié)點(diǎn)移動(dòng)到雙向鏈表的頭部。
雙向鏈表節(jié)點(diǎn)（哈希表的 value）的結(jié)構(gòu)如下：
class Node {int key;int value;Node prev;Node next;Node() {}Node(int key, int value) {this.key = key;this.value = value;}}
你可能會(huì)問(wèn)，哈希表的 value 為何還要存放 key？
這是因?yàn)椋?strong style="-webkit-tap-highlight-color: transparent;color: rgb(15, 76, 129);line-height: 1.75;">雙向鏈表有一個(gè)刪除尾節(jié)點(diǎn)的操作。我們定位到雙向鏈表的尾節(jié)點(diǎn)，在鏈表中刪除之后，還要找到該尾節(jié)點(diǎn)在哈希表中的位置，因此需要根據(jù) value 中存放的 key，定位到哈希表的數(shù)據(jù)項(xiàng)，然后將其刪除。
以下是 Java 版本代碼的完整實(shí)現(xiàn)。
class LRUCache {class Node {int key;int value;Node prev;Node next;Node() {}Node(int key, int value) {this.key = key;this.value = value;}}private int size;private int capacity;private Map<Integer, Node> cache;/* 虛擬頭節(jié)點(diǎn) */private Node head;/* 虛擬尾節(jié)點(diǎn) */private Node tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;cache = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}// 將最近這次訪問(wèn)的數(shù)據(jù)移到頭部moveToHead(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);if (node == null) {Node newNode = new Node(key, value);cache.put(key, newNode);// 將最近新增的數(shù)據(jù)放到頭部addToHead(newNode);++size;// 若數(shù)據(jù)量超過(guò)設(shè)定的最大容量，移除尾部（最不常訪問(wèn)）的節(jié)點(diǎn)數(shù)據(jù)if (size > capacity) {Node tail = removeTail();// 緩存淘汰，移除尾部節(jié)點(diǎn)數(shù)據(jù)cache.remove(tail.key);--size;}} else {node.value = value;moveToHead(node);}}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}private void addToHead(Node node) {node.next = head.next;head.next = node;node.next.prev = node;node.prev = head;}private Node removeTail() {Node node = tail.prev;removeNode(node);return node;}}
長(zhǎng)按識(shí)別下圖二維碼，關(guān)注公眾號(hào)「Doocs 開(kāi)源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。