LFU（LeastFrequently Used），即最近最多使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。LFU算法需要维护一个队列记录所有数据的访问记录，每个数据都需要维护引用计数。LFU算法需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序，性能消耗较高。
LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。具体实现如图4-1所示。
图4-1所示的操作包括：
（1）新加入数据插入到队列尾部（因为引用计数为1）；
（2）队列中的数据被访问后，引用计数增加，队列重新排序；
（3）当需要淘汰数据时，将已经排序的列表最后的数据块删除。
注意LFU和下一小节要介绍的LRU算法之间存在的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子，假设缓存大小为3，数据访问序列为set(2,2)、set(1,1)、get(2)、get(1)、get(2)、set(3,3)、set(4,4)，则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1)。LRU关键是看页面最后一次被使用到发生调度的时间长短，而LFU关键是看一定时间段内页面被使用的频率。
那么基于LFU算法的Cache设计应该支持的操作如。
n get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；
n set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最少访问的数据。
为了能够淘汰最少使用的数据，LFU算法最简单的一种设计思路就是利用一个数组存储数据项，用HashMap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
另外还有一种实现思路就是利用最小堆和HashMap两者的优势，最小堆中根结点的键值是所有堆结点键值中的最小者。最小堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。代码清单4-3所示的代码是最小堆实现的一个示例。
代码清单4-3 最小堆实现示例
public classSmallHeapDemo {
final static int MAX_LEN = 100;
private int queue[] = newint[MAX_LEN];
private int size;
public void add(int e){
if(size >= MAX_LEN)
{
System.err.println("overflow");
return;
}
int s = size++;
shiftup(s,e);
}
public int size(){
return size;
}
private void shiftup(int s, int e){
while(s > 0){
int parent = (s - 1)/2;
if(queue[parent] < e){
break;
}
queue[s] = queue[parent];
s = parent;
}
queue[s] = e;
}
public int poll(){
if(size <= 0)
return -1;
int ret = queue[0];
int s = --size;
shiftdown(0, queue[s]);
queue[s] = 0;
return ret;
}
private void shiftdown(int i, int e){
int half = size /2;
while(i < half ){
int child = 2*i +1;
int right = child +1;
if(right < size &&queue[child] > queue[right]){
child = right;
}
if(e < queue[child]){
break;
}
queue[i] = queue[child];
i = child;
}
queue[i] = e;
}
public static void main(Stringargs[]){
SmallHeapDemo hs = newSmallHeapDemo();
hs.add(4);
hs.add(3);
hs.add(7);
hs.add(2);
int size = hs.size();
for(int i=0; i< size; i++){
System.out.println(hs.poll());
}
}
}
程序运行输出为“2347”。
一般情况下，LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即LFU存在历史数据影响将来数据的“缓存污染”效用。
