因為希望是O(1)的時間復(fù)雜度,所以很容易想到需要使用哈希表。那么接下來，就直接講實現(xiàn)思路了。
??LRUCache 的常見實現(xiàn)方式是：哈希表+雙向鏈表。那為什么不是哈希表+數(shù)組了。因為數(shù)組的查找和替換是O(N)級別的，所以需要使用雙向鏈表。

思路：

說明：

map用來作為存儲容器，key是傳進(jìn)來的Int值，value是Node節(jié)點；即map[int] = node。

Node節(jié)點信息包含

{keyvalueprev：Nodenext：Node

　　　　　　3.LRUCache類包含:map, 以及first , last2 個虛擬的節(jié)點

　　　　　　圖中的first節(jié)點和last的節(jié)點都是虛節(jié)點，不存儲任何值，只是為了維持雙向鏈表的完整性。

完成這個LRUCache的核心思路是：在存和取的時候更新節(jié)點的位置。

如果該節(jié)點存在，執(zhí)行以下3步
如果該節(jié)點不存在
判斷是否已經(jīng)達(dá)到最大容量

取

如果沒有取到值，就直接返回-1
如果取到值了，就需要更新這個節(jié)點的位置
我們需要將它更新到first節(jié)點的后面。具體的執(zhí)行步驟有以下2步
刪除該結(jié)點,【也就是第5個節(jié)點】
把該結(jié)點添加到first節(jié)點的后面

存

存的時候，先去根據(jù)key獲取該結(jié)點信息
將其value的值更新一下
刪除該結(jié)點
并且將該節(jié)點添加到first節(jié)點的后面
如果不是，就將該結(jié)點添加到first節(jié)點后面
如果是，就將最后一個節(jié)點【last的prev節(jié)點】刪掉，然后將新節(jié)點添加到fisrt節(jié)點的后面

代碼如下：swift版本和java版本

class LRUCache { //【swift版本】
    private var map = [Int : Node]()
    private var capacity = 0
    private let first = Node(0, 0)
    private let last = Node(0, 0)
    
    init(_ capacity: Int) {
        self.capacity = capacity
        // 初始化指向
        first.next = last
        last.prev = first
    }
    
    func get(_ key: Int) -> Int {
        guard let node = map[key] else { return -1 }
        // 如果取到值了
        //1.先將該結(jié)點刪除掉,但是map不刪
        removeNode(node: node)
        //2.就將之插入到first節(jié)點的后面
        insertToFirstBehind(node: node)
        return node.value
    }
    
    func put(_ key: Int, _ value: Int) {
        
        guard let node = map[key] else {
            // 添加一對新的key-value
            if map.count == capacity {
                // 淘汰最近最少使用的 即刪掉last節(jié)點前的那個節(jié)點，并且map也刪
                let needDeleteNode = map.removeValue(forKey: last.prev!.key)!
                removeNode(node: needDeleteNode)
            }
            // 然后添加
            let node = Node(key, value)
            map[key] = node
            insertToFirstBehind(node: node)
            
            
            return
        }
        // 值不為空就更新下值
        node.value = value
        removeNode(node: node)
        insertToFirstBehind(node: node)
    }
    
    private func removeNode(node: Node) {
        node.next?.prev = node.prev
        node.prev?.next = node.next
    }
    
    private func insertToFirstBehind(node: Node) {
        // node 和 first.next
        first.next?.prev = node
        node.next = first.next
        //node 和 first
        first.next = node
        node.prev = first
    }
    
    class Node {
        public let key: Int
        public var value : Int
        public var prev: Node?
        public var next: Node?
        init(_ key: Int, _ value: Int) {
            self.key = key
            self.value = value
        }
    }
}

public class LRUCache { //【java版本】
    private Map<Integer, Node> map;
    private int capacity;
    // 虛擬頭結(jié)點
    private Node first;
    // 虛擬尾結(jié)點
    private Node last;
 
    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
    }
 
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
 
        removeNode(node);
        addAfterFirst(node);
 
        return node.value;
    }
 
    /**
     * @param node 將node節(jié)點插入到first節(jié)點的后面
     */
    private void addAfterFirst(Node node) {
        // node與first.next
        node.next = first.next;
        first.next.prev = node;
 
        // node與first
        first.next = node;
        node.prev = first;
    }
 
    /**
     * @param node 從雙向鏈表中刪除node節(jié)點
     */
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
 
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            removeNode(node);
        } else { // 添加一對新的key-value
            if (map.size() == capacity) {
                // 淘汰最近最少使用的node
                removeNode(map.remove(last.prev.key));
//                map.remove(last.prev.key);
//                removeNode(last.prev);
            }
            map.put(key, node = new Node(key, value));
        }
        addAfterFirst(node);
    }
 
    private static class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public Node() {}
    }
}

總結(jié)
??今天主要講了LRU緩存的實現(xiàn)思路，以及具體的代碼實現(xiàn)。其核心就是在存取的時候完成整個LRU算法的一個運轉(zhuǎn)，保持最先最少使用的被淘汰，然后一直運轉(zhuǎn)下去。使用的數(shù)據(jù)結(jié)構(gòu)是大家比較熟悉的字典和雙向鏈表。希望能幫助到大家。

歡迎關(guān)注【無量測試之道】公眾號，回復(fù)【領(lǐng)取資源】
Python編程學(xué)習(xí)資源干貨、
Python+Appium框架APP的UI自動化、
Python+Selenium框架Web的UI自動化、
Python+Unittest框架API自動化、
資源和代碼 免費送啦~
文章下方有公眾號二維碼，可直接微信掃一掃關(guān)注即可。

備注：我的個人公眾號已正式開通，致力于測試技術(shù)的分享，包含：大數(shù)據(jù)測試、功能測試，測試開發(fā)，API接口自動化、測試運維、UI自動化測試等，微信搜索公眾號：“無量測試之道”，或掃描下方二維碼：

添加關(guān)注，讓我們一起共同成長！

總結(jié)

以上是生活随笔為你收集整理的LRU 缓存机制的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。