之前面試被問到了LRU Cache，之前沒接觸，現(xiàn)在學習補充一下。

什么是Cache

Cache概念

Cache，即高速緩存，是介于CPU和內存之間的高速小容量存儲器。在金字塔式存儲體系中它位于自頂向下的第二層，僅次于CPU寄存器。其容量遠小于內存，但速度卻可以接近CPU的頻率。

當CPU發(fā)出內存訪問請求時，會先查看 Cache 內是否有請求數(shù)據(jù)。

如果存在（命中），則直接返回該數(shù)據(jù)
如果不存在（失效），再去訪問內存 —— 先把內存中的相應數(shù)據(jù)載入緩存，再將其返回處理器

提供“高速緩存”的目的是讓數(shù)據(jù)訪問的速度適應CPU的處理速度，通過減少訪問內存的次數(shù)來提高數(shù)據(jù)存取的速度。

Cache原理

Cache 技術所依賴的原理是”程序執(zhí)行與數(shù)據(jù)訪問的局部性原理“，這種局部性表現(xiàn)在兩個方面：

時間局部性：如果程序中的某條指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行，如果某數(shù)據(jù)被訪問過，不久以后該數(shù)據(jù)可能再次被訪問。
空間局部性：一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的范圍之內，這是因為指令或數(shù)據(jù)通常是順序存放的。

時間局部性是通過將近來使用的指令和數(shù)據(jù)保存到Cache中實現(xiàn)。
空間局部性通常是使用較大的高速緩存，并將預取機制集成到高速緩存控制邏輯中來實現(xiàn)。

Cache替換策略

Cache的容量是有限的，當Cache的空間都被占滿后，如果再次發(fā)生緩存失效，就必須選擇一個緩存塊來替換掉。常用的替換策略有以下幾種：

隨機算法（Rand）：隨機法是隨機地確定替換的存儲塊。設置一個隨機數(shù)產生器，依據(jù)所產生的隨機數(shù)，確定替換塊。這種方法簡單、易于實現(xiàn)，但命中率比較低。
先進先出算法（FIFO, First In First Out）：先進先出法是選擇那個最先調入的那個塊進行替換。當最先調入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機法好些，但還不滿足要求。
最久未使用算法（LRU, Least Recently Used）：LRU法是依據(jù)各塊使用的情況，總是選擇那個最長時間未被使用的塊替換。這種方法比較好地反映了程序局部性規(guī)律。
最不經常使用算法（LFU, Least Frequently Used）：將最近一段時期內，訪問次數(shù)最少的塊替換出Cache。

Cache概念的擴充

如今高速緩存的概念已被擴充，不僅在CPU和主內存之間有Cache，而且在內存和硬盤之間也有Cache（磁盤緩存），乃至在硬盤與網(wǎng)絡之間也有某種意義上的Cache──稱為Internet臨時文件夾或網(wǎng)絡內容緩存等。凡是位于速度相差較大的兩種硬件之間，用于協(xié)調兩者數(shù)據(jù)傳輸速度差異的結構，均可稱之為Cache。

LRU總覽

LRU全稱是Least Recently Used，即最近最久未使用的意思。LRU算法的設計原則是：如果一個數(shù)據(jù)在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。是緩存中一種常見的機制。

LRU

LRU淘汰

cache（緩存）可以幫助快速存取數(shù)據(jù)，但是容量小

LRU的思想來自“最近用到的數(shù)據(jù)被重用的概率比最早用到的數(shù)據(jù)大的多”，是一種十分高效的cache。

他的算法就是當緩存空間滿了的時候，將最近最少使用的數(shù)據(jù)從緩存空間中刪除以增加可用的緩存空間來緩存新內容。是一個淘汰策略。

這個算分的內部有一個緩存列表。每當一個緩存數(shù)據(jù)被訪問的時候，這個數(shù)據(jù)就會被提到列表頭部，每次都這樣的話，列表的尾部數(shù)據(jù)就是最近最不常使用的了，當緩存空間不足時，就會刪除列表尾部的緩存數(shù)據(jù)。

直接用hashmap無法實現(xiàn)，查找復雜度接近O(1)，但是不能保證存儲的是有效的數(shù)據(jù)。

LRU分析

簡單的說，就是保證基本的get和set的功能的同時，還要保證最近訪問(get或put)的節(jié)點保持在限定容量的Cache中，如果超過容量則應該把LRU(近期最少使用)的節(jié)點刪除掉。

那么我們思考一個問題：如何設計實現(xiàn)一個LRU Cache？
那么，我們可能需要使用類似這樣的數(shù)據(jù)結構去實現(xiàn)這個LRU Cache：

LRU Cache

通過雙向鏈表來保證LRU的刪除和更新操作也能保證O(1)的復雜度。

LRU實現(xiàn)

原則就是：每當訪問鏈表時都更新鏈表節(jié)點

若只是用雙向鏈表呢？

對一個Cache的操作無非三種：插入(insert)、替換(replace)、查找（lookup）

為了能夠快速刪除最久沒有訪問的數(shù)據(jù)項和插入最新的數(shù)據(jù)項，我們使用雙向鏈表連接Cache中的數(shù)據(jù)項，并且保證鏈表維持數(shù)據(jù)項從最近訪問到最舊訪問的順序。

插入(insert)
當Cache未滿時，新的數(shù)據(jù)項只需插到雙鏈表頭部即可。時間復雜度為 $O(1)$ .
替換(replace) = insert + delete
當Cache已滿時，將新的數(shù)據(jù)項插到雙鏈表頭部，并刪除雙鏈表的尾結點即可。時間復雜度為 $O(1)$ .
查找（lookup）
每次數(shù)據(jù)項被查詢到時，都將此數(shù)據(jù)項移動到鏈表頭部。

經過分析，我們知道使用雙向鏈表可以保證插入和替換的時間復雜度是 $O(1)$ ，但查詢的時間復雜度是 $O(n)$ ，因為需要對雙鏈表進行遍歷。為了讓查找效率也達到 $O(1)$ ，很自然的會想到使用 hash table 。

雙向鏈表+HashMap

對于雙向鏈表的使用，基于兩個考慮。

Cache中塊的命中是隨機的，和Load進來的順序無關。
雙向鏈表插入、刪除很快，可以靈活的調整相互間的次序，時間復雜度為O(1)。

1. Node節(jié)點

新建數(shù)據(jù)類型Node節(jié)點，Key-Value值，并有指向前驅節(jié)點后后繼節(jié)點的指針，構成雙向鏈表的節(jié)點。

class Node {
    int key;
    int value;
    Node pre;
    Node next;
 
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
    
    @Override
    public String toString() {
        return this.key + "-" + this.value + " ";
    }
}

2. int get(int key)

鏈表順序:從最近訪問到最舊訪問

為了能夠快速刪除最久沒有訪問的數(shù)據(jù)項和插入最新的數(shù)據(jù)項，我們將雙向鏈表連接Cache中的數(shù)據(jù)項，并且保證鏈表維持數(shù)據(jù)項從最近訪問到最舊訪問的順序。

每次數(shù)據(jù)項被查詢到時，都將此數(shù)據(jù)項移動到鏈表頭部（ $O(1)$ 的時間復雜度）

這樣，在進行過多次查找操作后，最近被使用過的內容就向鏈表的頭移動，而沒有被使用的內容就向鏈表的后面移動。

當需要替換時，鏈表最后的位置就是最近最少被使用的數(shù)據(jù)項，我們只需要將最新的數(shù)據(jù)項放在鏈表頭部，當Cache滿時，淘汰鏈表最后的位置就是了。

解決了LRU的特性，現(xiàn)在考慮下算法的時間復雜度。為了能減少整個數(shù)據(jù)結構的時間復雜度，就要減少查找的時間復雜度，所以這里利用HashMap來做，這樣時間復雜度就是O(1)。

所以對于本題來說：

設計

如果cache中不存在要get的值，返回-1
如果cache中存在要找的值，返回其值，并將其在原鏈表中刪除，然后將其插入作為頭結點。

public int get(int key) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            remove(n);//刪除
            setHead(n);//插入頭
            printNodes("get");//用于測試
            return n.value;
        }
        printNodes("get");
        return -1;
    }

3. set(int key, int value)

set(key,value)：

當set的key值已經存在，就更新其value，將其在原鏈表中刪除，然后將其插入作為頭結點
當set的key值不存在，就新建一個node
2.1 如果當前len<capacity,就將其加入hashmap中，并將其作為頭結點，更新len長度
2.2 否則，刪除鏈表最后一個node，再將其放入hashmap并作為頭結點，但len不更新。

public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node old = map.get(key);
            old.value = value;
            remove(old);//刪除
            setHead(old);//插入頭
        } else {
            Node created = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(end.key);//map刪除
                remove(end);//刪除
                setHead(created);
            } else {
                setHead(created);
            }
            map.put(key, created);
        }
        printNodes("set");
    }

最后附上完整源代碼及輸出結果如下：

public class LRUCache3 {
    class Node {
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return this.key + ":" + this.value + " ";
        }
    }

    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head = null;
    Node end = null;

    public LRUCache3(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            remove(n);
            setHead(n);
            printNodes("get");
            return n.value;
        }
        printNodes("get");
        return -1;
    }

    public void remove(Node n) {
        if (n.pre != null) {
            n.pre.next = n.next;
        } else {
            head = n.next;
        }

        if (n.next != null) {
            n.next.pre = n.pre;
        } else {
            end = n.pre;
        }

    }

    public void setHead(Node n) {
        n.next = head;
        n.pre = null;

        if (head != null)
            head.pre = n;

        head = n;

        if (end == null)
            end = head;
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        } else {
            Node created = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(end.key);
                remove(end);
                setHead(created);

            } else {
                setHead(created);
            }

            map.put(key, created);
        }
        printNodes("set");
    }

    public void printNodes(String explain) {

        System.out.print(explain + ":" + head.toString());
        Node node = head.next;
        while (node != null) {
            System.out.print(node.toString());
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache3 lruCache3 = new LRUCache3(5);
        lruCache3.set(1, 100);
        lruCache3.set(2, 200);
        lruCache3.set(3, 300);
        lruCache3.set(4, 400);
        lruCache3.set(5, 500);
        System.out.println("lruCacheTest.get(1):" + lruCache3.get(1));
        lruCache3.set(6, 600);
        System.out.println("lruCacheTest.get(2):" + lruCache3.get(2));
    }
}

輸出：

set:1:100 
set:2:200 1:100 
set:3:300 2:200 1:100 
set:4:400 3:300 2:200 1:100 
set:5:500 4:400 3:300 2:200 1:100 
get:1:100 5:500 4:400 3:300 2:200 
lruCacheTest.get(1):100
set:6:600 1:100 5:500 4:400 3:300 
get:6:600 1:100 5:500 4:400 3:300 
lruCacheTest.get(2):-1

基于LinkedHashMap的實現(xiàn)

緩存這個東西就是為了提高運行速度的，由于緩存是在寸土寸金的內存里面，不是在硬盤里面，所以容量是很有限的。LRU這個算法就是把最近一次使用時間離現(xiàn)在時間最遠的數(shù)據(jù)刪除掉。

LinkedHashMap默認的元素順序是put的順序，但是如果使用帶參數(shù)的構造函數(shù)，那么LinkedHashMap會根據(jù)訪問順序來調整內部順序。 LinkedHashMap的get()方法除了返回元素之外還可以把被訪問的元素放到鏈表的底端，這樣一來每次頂端的元素就是remove的元素。

構造函數(shù)

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；

initialCapacity
初始容量
loadFactor
加載因子，一般是 0.75f
accessOrder
false 基于插入順序
true 基于訪問順序（get一個元素后，這個元素被加到最后，使用了LRU 最近最少被使用的調度算法）

removeEldestEntry(Map.Entry<K,V> eldest)

LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認返回false，即不刪除老數(shù)據(jù)
我們要做的就是重寫這個方法，當滿足一定條件時刪除老數(shù)據(jù)

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

實現(xiàn)

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 簡單用LinkedHashMap來實現(xiàn)的LRU算法的緩存
 */
public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;

    public LRUCache2(int cacheSize) {
        super(16, (float) 0.75, true);
        this.cacheSize = cacheSize;
    }

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }

    public static void main(String[] args) {
        LRUCache2<Integer, Integer> lruCache2 = new LRUCache2<>(5);
        lruCache2.put(1, 100);
        lruCache2.put(2, 200);
        lruCache2.put(3, 300);
        lruCache2.put(4, 400);
        lruCache2.put(5, 500);
        System.out.println("LRUCache2.get(1):" + lruCache2.get(1));
        lruCache2.put(6, 600);
        System.out.println("LRUCache2.get(2):" + lruCache2.get(2));
    }
}

輸出：

LRUCache2.get(1):100
LRUCache2.get(2):null

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LRU Cache

LRU Cache

什么是Cache

Cache概念

Cache原理

Cache替換策略

Cache概念的擴充

LRU總覽

LRU淘汰

LRU分析

LRU實現(xiàn)

若只是用雙向鏈表呢？

雙向鏈表+HashMap

1. Node節(jié)點

2. int get(int key)

鏈表順序:從最近訪問到最舊訪問

設計

3. set(int key, int value)

基于LinkedHashMap的實現(xiàn)

構造函數(shù)

removeEldestEntry(Map.Entry<K,V> eldest)

實現(xiàn)

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LRU Cache

什么是Cache

Cache概念

Cache原理

Cache替換策略

Cache概念的擴充

LRU總覽

LRU淘汰

LRU分析

LRU實現(xiàn)

若只是用雙向鏈表呢？

雙向鏈表+HashMap

1. Node節(jié)點

2. int get(int key)

鏈表順序:從最近訪問到最舊訪問

設計

3. set(int key, int value)

基于LinkedHashMap的實現(xiàn)

構造函數(shù)

removeEldestEntry(Map.Entry<K,V> eldest)

實現(xiàn)

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av