上篇文章介绍了LRU算法，今天打算介绍一下LFU算法。上一篇文章提到过，LFU（Leastfrequentlyused：最少使用）算法和LRU算法只是淘汰策略不同。LRU倾向于保留最近使用过的数据，而LFU倾向于保留使用频率较高的数据。举个简单的：缓存中有A、B两条数据，已经达到上限。如果先访问数据A10次，再访问数据B一次，当新的数据C存入时，如果当前的LRU算法会淘汰数据A，如果是LFU算法则会淘汰数据B。至简单来说，在LRU算法中，不管访问频率如何，只要是最近访问过的，就不会淘汰数据。在LFU算法中，访问频率作为权重。只要访问频率越高，数据就会被淘汰。它被淘汰的可能性越小，即使数据已经很长时间没有被访问过。算法实现我们还是通过一段JavaScript代码来实现这个逻辑。classLFUCache{freqs={}//用于标记访问频率cache={}//用于缓存所有数据capacity=0//缓存构造函数的最大容量(capacity){//存储最大可以访问的容量被LFUthis缓存。capacity=capacity}}和LRU算法一样，LFU算法也需要实现get和put方法来获取和设置缓存。classLFUCache{//获取缓存get(key){}//设置缓存put(key,value){}}老规矩，先看设置缓存的部分。如果缓存的键之前存在，则需要更新其值。classLFUCache{//cache是??缓存的存储对象//其解构为：{key:{freq:0,value:''}}//freq表示读取数据的频率；//value表示缓存的数据；cache={}//用于存储缓存数据的fregs的频率//其解构为：{0:[a],1:[b,c],2:[d]}//表示a尚未被读取,b/c各读一次，d读两次freqs={}//设置缓存put(key,value){//先判断缓存是否存在constcache=this.cache[key]if(cache){//如果存在，则重置缓存值cache.value=value//更新使用频率let{freq}=cache//从freqs中获取key对应的const数组keys=this.freqs[freq]constindex=keys.indexOf(key)//从频率数组中删除对应的keykeys.splice(index,1)if(keys.length===0){//如果当前频率不存在key//就会bekeydeletedeletethis.freqs[freq]}//更新频率加1freq=(cache.freq+=1)//更新频率数组constfreqMap=this.freqs[freq]||(this.freqs[freq]=[])freqMap.push(key)return}}}如果缓存不存在，先判断缓存是否超出容量。如果是这样，则需要剔除使用频率最低的数据。classLFUCache{//更新频率active(key,cache){//更新频率let{freq}=cache//从freqs中获取key对应的数组constkeys=this.freqs[freq]constindex=keys.indexOf(key)//从频率数组中删除对应的keykeys.splice(index,1)if(keys.length===0){//如果当前频率不存在key//删除keydeletethis.freqs[freq]}//更新频率加1freq=(cache.freq+=1)//更新读取频率数组constfreqMap=this.freqs[freq]||(this.freqs[freq]=[])freqMap.push(key)}//设置缓存put(key,value){//先判断缓存是否存在constcache=this.cache[key]if(cache){//如果存在，则重置缓存的值cache.value=valuethis.active(key,cache)return}//判断缓存是否超过容量constlist=Object.keys(this.cache)if(list.length>=this.capacity){//超过存储大小，删除访问频率最低的数据const[first]=Object.keys(this.freqs)constkeys=this.freqs[first]constlatest=keys.shift()删除this.cache[latest]if(keys.length===0)deletethis.freqs[latest]}//写入缓存，默认频率为0，表示还没有被使用。this.cache[key]={value,freq:0}//读写频率数组constfreqMap=this.freqs[0]||(this.freqs[0]=[])freqMap.push(key)}}实现设置缓存的方法后，很容易获取缓存类LRUCache{//获取数据get(key){if(this.cache[key]!==undefined){//如果key对应的缓存存在，则更新其读取频率//之前已经实现了，this.active(key)可以直接复用returnthis.cache[key]}returnundefined}}LFU缓存算法执行到此结束。当然，算法一般都是以双向链表的形式实现的。这里的实现方法只是为了方便理解其原理。有兴趣的可以上网搜索更高效的实现方式。
