我們本期來分析一下LFU：

LFU是什么

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

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

LRU實現(xiàn)

2.1 定義Node節(jié)點

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

/** * 節(jié)點 */ public static class Node implements Comparable<Node>{ //鍵 Object key; //值 Object value; /** * 訪問時間 */ long time; /** * 訪問次數(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ù)目相同的情況下 比較時間 if (compare==0){ return Long.compare(this.time，o.time);
        } return compare;
    }
}

2.2:定義LFU類

定義LFU類，這里采用了泛型，聲明了K和V，還有總容量和一個Map(caches)用來維護所有的節(jié)點。在構造方法里將size傳遞進去，并且創(chuàng)建了一個LinkedHashMap，采用linkedHashMap的主要原因是維護key的順序

public class LFU<K，V> { /** *  總容量 */ private int capacity; /** * 所有的node節(jié)點 */ private Map caches; /** * 構造方法
     * @param size */ public LFU(int size) { this.capacity = size;
       caches = new LinkedHashMap(size);
    }
}

2.3: 添加元素

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

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

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

** 移除最小的元素**

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

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

 }

2.4:獲取元素

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

此時不能將它直接移動到鏈表頂，還需要進行一次排序，重組它的位置~

/** * 獲取元素
 * @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;
}

測試

首先聲明一個LRU，然后默認的最大的大小為5，依次put進入A、B、C、D、E、F6個元素，此時將會找到計數(shù)最小和時間最短的元素，那么將會淘汰A(因為count值都是1)。記著get兩次B元素，那么B元素的count=3，時間更新為最新。此時B將會移動到頂，接著在getC元素，C元素的count=2，時間會最新，那么此時因為它的count值依然小于B，所以它依然在B后面，再getF元素，F(xiàn)元素的count=2，又因為它的時間會最新，所以在與C相同的計數(shù)下，F(xiàn)元素更新(時間距離現(xiàn)在最近)，所以鏈表將會移動，F(xiàn)會在C的前面，再次put一次C，此時C的count=3，同時時間為最新，那么此刻C的count和B保持一致，則他們比較時間，C明顯更新，所以C將會排在B的前面，最終的順序應該是: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é)點3 lruCache.put(3，"C"); final Map caches = (Map) lruCache.caches; for (Map.Entry nodeEntry : caches.entrySet()) { 
        System.out.println(nodeEntry.getValue().value); 
    } 
}

運行結果：

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

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

總結

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