字節(jié)二面，讓寫(xiě)一個(gè)LFU緩存策略算法，懵了

我們本期來(lái)分析一下LFU：

LFU是什么

LFU，全稱是:Least Frequently Used，最不經(jīng)常使用策略，在一段時(shí)間內(nèi)，數(shù)據(jù)被使用頻次最少的，優(yōu)先被淘汰。最少使用（LFU）是一種用于管理計(jì)算機(jī)內(nèi)存的緩存算法。主要是記錄和追蹤內(nèi)存塊的使用次數(shù)，當(dāng)緩存已滿并且需要更多空間時(shí)，系統(tǒng)將以最低內(nèi)存塊使用頻率清除內(nèi)存.采用LFU算法的最簡(jiǎn)單方法是為每個(gè)加載到緩存的塊分配一個(gè)計(jì)數(shù)器。每次引用該塊時(shí)，計(jì)數(shù)器將增加一。當(dāng)緩存達(dá)到容量并有一個(gè)新的內(nèi)存塊等待插入時(shí)，系統(tǒng)將搜索計(jì)數(shù)器最低的塊并將其從緩存中刪除(本段摘自維基百科)

上面這個(gè)圖就是一個(gè)LRU的簡(jiǎn)單實(shí)現(xiàn)思路，在鏈表的開(kāi)始插入元素，然后每插入一次計(jì)數(shù)一次，接著按照次數(shù)重新排序鏈表，如果次數(shù)相同的話，按照插入時(shí)間排序，然后從鏈表尾部選擇淘汰的數(shù)據(jù)~

LRU實(shí)現(xiàn)

2.1 定義Node節(jié)點(diǎn)

Node主要包含了key和value，因?yàn)長(zhǎng)FU的主要實(shí)現(xiàn)思想是比較訪問(wèn)的次數(shù)，如果在次數(shù)相同的情況下需要比較節(jié)點(diǎn)的時(shí)間，越早放入的越快      被淘汰，因此我們需要在Node節(jié)點(diǎn)上加入time和count的屬性，分別用來(lái)記錄節(jié)點(diǎn)的訪問(wèn)的時(shí)間和訪問(wèn)次數(shù)。其他的版本實(shí)現(xiàn)方式里有新加個(gè)內(nèi)部類來(lái)記錄 key的count和time，但是我覺(jué)得不夠方便，還得單獨(dú)維護(hù)一個(gè)map，成本有點(diǎn)大。還有一點(diǎn)注意的是這里實(shí)現(xiàn)了comparable接口，覆寫(xiě)了compare方法，這里 的主要作用就是在排序的時(shí)候需要用到，在compare方法里面我們首先比較節(jié)點(diǎn)的訪問(wèn)次數(shù)，在訪問(wèn)次數(shù)相同的情況下比較節(jié)點(diǎn)的訪問(wèn)時(shí)間，這里是為了 在排序方法里面通過(guò)比較key來(lái)選擇淘汰的key

/** * 節(jié)點(diǎn) */ public static class Node implements Comparable<Node>{ //鍵 Object key; //值 Object value; /** * 訪問(wèn)時(shí)間 */ long time; /** * 訪問(wèn)次數(shù) */ int count; public Node(Object key， Object value， long time， int count) { this.key = key; this.value = value; this.time = time; this.count = count;
    } public Object getKey() { return key;
    } public void setKey(Object key) { this.key = key;
    } public Object getValue() { return value;
    } public void setValue(Object value) { this.value = value;
    } public long getTime() { return time;
    } public void setTime(long time) { this.time = time;
    } public int getCount() { return count;
    } public void setCount(int count) { this.count = count;
    } @Override public int compareTo(Node o) { int compare = Integer.compare(this.count， o.count); //在數(shù)目相同的情況下 比較時(shí)間 if (compare==0){ return Long.compare(this.time，o.time);
        } return compare;
    }
}

2.2:定義LFU類

定義LFU類，這里采用了泛型，聲明了K和V，還有總?cè)萘亢鸵粋€(gè)Map(caches)用來(lái)維護(hù)所有的節(jié)點(diǎn)。在構(gòu)造方法里將size傳遞進(jìn)去，并且創(chuàng)建了一個(gè)LinkedHashMap，采用linkedHashMap的主要原因是維護(hù)key的順序

public class LFU<K，V> { /** *  總?cè)萘?nbsp;*/ private int capacity; /** * 所有的node節(jié)點(diǎn) */ private Map caches; /** * 構(gòu)造方法
     * @param size */ public LFU(int size) { this.capacity = size;
       caches = new LinkedHashMap(size);
    }
}

2.3: 添加元素

添加元素的邏輯主要是先從緩存中根據(jù)key獲取節(jié)點(diǎn)，如果獲取不到，證明是新添加的元素，然后和容量比較，大于預(yù)定容量的話，需要找出count計(jì)數(shù)最小(計(jì)數(shù)相同的情況下，選擇時(shí)間最久)的節(jié)點(diǎn)，然后移除掉那個(gè)。如果在預(yù)定的大小之內(nèi)，就新創(chuàng)建節(jié)點(diǎn)，注意這里不能使用 System.currentTimeMillis()方法，因?yàn)楹撩爰?jí)別的粒度無(wú)法對(duì)插入的時(shí)間進(jìn)行區(qū)分，在運(yùn)行比較快的情況下，只有System.nanoTime()才可以將key的插入時(shí)間區(qū)分，默認(rèn)設(shè)置count計(jì)數(shù)為1.如果能獲取到，表示是舊的元素，那么就用新值覆蓋舊值，計(jì)數(shù)+1，設(shè)置key的time為當(dāng)前納秒時(shí)間。最后還需要進(jìn)行排序，這里可以看出插入元素的邏輯主要是添加進(jìn)入緩存，更新元素的時(shí)間和計(jì)數(shù)~

/** * 添加元素
 * @param key
 * @param value */ public void put(K key， V value) {
    Node node = caches.get(key); //如果新元素 if (node == null) { //如果超過(guò)元素容納量 if (caches.size() >= capacity) { //移除count計(jì)數(shù)最小的那個(gè)key K leastKey = removeLeastCount();
            caches.remove(leastKey);
        } //創(chuàng)建新節(jié)點(diǎn) node = new Node(key，value，System.nanoTime()，1);
        caches.put(key， node);
    }else { //已經(jīng)存在的元素覆蓋舊值 node.value = value;
        node.setCount(node.getCount()+1);
        node.setTime(System.nanoTime());
    }
    sort();
}

每次put或者get元素都需要進(jìn)行排序，排序的主要意義在于按照key的cout和time進(jìn)行一個(gè)key順序的重組，這里的邏輯是首先將緩存map創(chuàng)建成一個(gè)list，然后按照Node的value進(jìn)行，重組整個(gè)map。然后將原來(lái)的緩存清空，遍歷這個(gè)map， 把key和value的值放進(jìn)去原來(lái)的緩存中的順序就進(jìn)行了重組~這里區(qū)分于LRU的不同點(diǎn)在于使用了java的集合API，LRU的排序是進(jìn)行節(jié)點(diǎn)移動(dòng)。而在LFU中實(shí)現(xiàn)比較復(fù)雜，因?yàn)閜ut的時(shí)候不光得比較基數(shù)還有時(shí)間。如果不借助java的API的話，可以新維護(hù)一個(gè)節(jié)點(diǎn)頻率鏈表，每次將key保存在這個(gè)節(jié)點(diǎn)頻率鏈表中移動(dòng)指針，從而也間接可以實(shí)現(xiàn)排序~

/** * 排序 */ private void sort() {

    List> list = new ArrayList<>(caches.entrySet());
    Collections.sort(list， new Comparator>() { @Override public int compare(Map.Entry o1， Map.Entry o2) { return o2.getValue().compareTo(o1.getValue());
        }
    });

    caches.clear(); for (Map.Entry kNodeEntry : list) {
        caches.put(kNodeEntry.getKey()，kNodeEntry.getValue());
    }
}

** 移除最小的元素**

淘汰最小的元素這里調(diào)用了Collections.min方法，然后通過(guò)比較key的compare方法，找到計(jì)數(shù)最小和時(shí)間最長(zhǎng)的元素，直接從緩存中移除~

/** * 移除統(tǒng)計(jì)數(shù)或者時(shí)間比較最小的那個(gè)
 * @return */ private K removeLeastCount() {
    Collectionvalues = caches.values();
    Node min = Collections.min(values); return (K)min.getKey();

 }

2.4:獲取元素

獲取元素首先是從緩存map中獲取，否則返回null，在獲取到元素之后需要進(jìn)行節(jié)點(diǎn)的更新，計(jì)數(shù)+1和刷新節(jié)點(diǎn)的時(shí)間，根據(jù)LFU的原則，在當(dāng)前時(shí)間獲取到這個(gè)節(jié)點(diǎn)以后，這個(gè)節(jié)點(diǎn)就暫時(shí)變成了熱點(diǎn)節(jié)點(diǎn)，但是它的cout計(jì)數(shù)也有可能是小于某個(gè)節(jié)點(diǎn)的count的，所以

此時(shí)不能將它直接移動(dòng)到鏈表頂，還需要進(jìn)行一次排序，重組它的位置~

/** * 獲取元素
 * @param key
 * @return */ public V get(K key){
Node node = caches.get(key); if (node!=null){
    node.setCount(node.getCount()+1);
    node.setTime(System.nanoTime());
    sort(); return (V)node.value;
} return null;
}

測(cè)試

首先聲明一個(gè)LRU，然后默認(rèn)的最大的大小為5，依次put進(jìn)入A、B、C、D、E、F6個(gè)元素，此時(shí)將會(huì)找到計(jì)數(shù)最小和時(shí)間最短的元素，那么將會(huì)淘汰A(因?yàn)閏ount值都是1)。記著get兩次B元素，那么B元素的count=3，時(shí)間更新為最新。此時(shí)B將會(huì)移動(dòng)到頂，接著在getC元素，C元素的count=2，時(shí)間會(huì)最新，那么此時(shí)因?yàn)樗腸ount值依然小于B，所以它依然在B后面，再getF元素，F(xiàn)元素的count=2，又因?yàn)樗臅r(shí)間會(huì)最新，所以在與C相同的計(jì)數(shù)下，F(xiàn)元素更新(時(shí)間距離現(xiàn)在最近)，所以鏈表將會(huì)移動(dòng)，F(xiàn)會(huì)在C的前面，再次put一次C，此時(shí)C的count=3，同時(shí)時(shí)間為最新，那么此刻C的count和B保持一致，則他們比較時(shí)間，C明顯更新，所以C將會(huì)排在B的前面，最終的順序應(yīng)該是:C->B->F->E->D

public static void main(String[] args) {

    LFU lruCache = new LFU<>(5);
    lruCache.put(1， "A");
    lruCache.put(2， "B");
    lruCache.put(3， "C");
    lruCache.put(4， "D");
    lruCache.put(5， "E");
    lruCache.put(6， "F");
    lruCache.get(2);
    lruCache.get(2);
    lruCache.get(3);
    lruCache.get(6); //重新put節(jié)點(diǎn)3 lruCache.put(3，"C"); final Map caches = (Map) lruCache.caches; for (Map.Entry nodeEntry : caches.entrySet()) { 
        System.out.println(nodeEntry.getValue().value); 
    } 
}

運(yùn)行結(jié)果：

LRU和LFU的區(qū)別以及LFU的缺點(diǎn)

LRU和LFU側(cè)重點(diǎn)不同，LRU主要體現(xiàn)在對(duì)元素的使用時(shí)間上，而LFU主要體現(xiàn)在對(duì)元素的使用頻次上。LFU的缺陷是：在短期的時(shí)間內(nèi)，對(duì)某些緩存的訪問(wèn)頻次很高，這些緩存會(huì)立刻晉升為熱點(diǎn)數(shù)據(jù)，而保證不會(huì)淘汰，這樣會(huì)駐留在系統(tǒng)內(nèi)存里面。而實(shí)際上，這部分?jǐn)?shù)據(jù)只是短暫的高頻率訪問(wèn)，之后將會(huì)長(zhǎng)期不訪問(wèn)，瞬時(shí)的高頻訪問(wèn)將會(huì)造成這部分?jǐn)?shù)據(jù)的引用頻率加快，而一些新加入的緩存很容易被快速刪除，因?yàn)樗鼈兊囊妙l率很低。

總結(jié)

本篇博客針對(duì)LFU做了一個(gè)簡(jiǎn)單的介紹，并詳細(xì)介紹了如何用java來(lái)實(shí)現(xiàn)LFU，并且和LRU做了一個(gè)簡(jiǎn)單的比較。針對(duì)一種緩存策略。LFU有自己的獨(dú)特使用場(chǎng)景，如何實(shí)現(xiàn)LFU和利用LFU的特性來(lái)實(shí)現(xiàn)開(kāi)發(fā)過(guò)程部分功能是我們需要思考的。實(shí)際在使用中LRU的使用頻率要高于LFU，不過(guò)了解這種算法也算是程序員的必備技能。