缓存算法(FIFO、LRU、LFU三种算法的区别) FIFO算法# FIFO算法是一种比较容易实现的算法。 其思想是先进先出(FIFO，队伍)，这是最简单公平的思想，如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。空间满的时候，最先进入的数据会被最早置换（淘汰）掉
FIFO算法描述：设计在生成时确定大小的缓存结构，假设大小为k，它具有以下两个功能：
将set(key，value ) :记录(key，value )插入结构中。 当缓存已满时，它将替换最初进入缓存的数据。 get(key ) :返回与key对应的值。 实现：维护FIFO队列，将每个数据(分配的页面)按时间顺序链接组成队列，并将替换指针指向队列的开头。 进行再置换的情况下，依次调换置换指针所指示的数据(页面)，将新追加的数据插入队列的最后即可。
缺点：判断一个页面替换算法优劣的指标是缺页率，而FIFO算法的一个显著缺点是在某个特定时刻，缺页率随着页面的分配反而增加。 将其称为Belady现象。 Belady现象的原因是FIFO替换算法与进程访问内存的动态特征不兼容，被替换的内存页面经常被访问，或者进程没有分配足够的页面，因此FIFO算法导致了部分页面因此，请参阅现在不再使用FIFO算法
LRU算法LRU (最近未使用的算法)是一种常用的缓存算法，广泛应用于许多分布式缓存系统，如Redis、Memcached等。
LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）
LRU算法描述：设计在生成时确定大小的缓存结构，假设大小为k，它具有以下两个功能：
将set(key，value ) :记录(key，value )插入结构中。 当缓存已满时，它将替换最长时间未使用的数据。 get(key ) :返回与key对应的值。 实现：最朴素的思想是使用数组时间戳方式，但这是低效的。 因此，Java可由具有对应数据结构LinkedHashMap的双向链表(链接列表) HashMap )来实现。
LInkedHashMap#利用Java的LinkedHashMap，用非常简单的代码实现基于LRU算法的Cache功能
import java.util.LinkedHashMap； import java.util.Map； /**LinkedHashmap轻松实现的LRU算法缓存*/public class LRUCacheK，V extends LinkedHashMapK，V { private int cacheSize； publiclrucache(intcachesize ) super ) 16，) ) float ) 0.75，true )； this.cacheSize=cacheSize； } protectedbooleanremoveeldestentry (map.entryk，V eldest ) { return size } cachesize； }测试：
import org.slf4j.Logger； import org.slf4j.LoggerFactory； publicclasslrucachetest { privatestaticfinalloggerlog=logger factory.getlogger (lrucachetest.class )； 专用静态lrucachestring，integercache=newLrucache(10； publicstaticvoidmain (string [ ] args ) for ) intI=0； i 10； I ) cache.put(k'I，I )； }log.info('allcache:'{} '，cache )； cache.get('K3 )； log.info('getk3:'{} '，cache )； cache.get('K4 )； log.info('getk4:'{} '，cache )； cache.get('K4 )； log.info('getk4:'{} '，cache )； che.put (' k ' 10，10 )； log.info (afterrunningthelrualgorithmcache : ' { } '，cache )； }} Output:
all cache :'{k0=0，k1=1，k2=2，k3=3，k4=4，k5=5，k6=6，k7=7，k8=8，K9=9} ' getk 3: ' { kk k4=4} ' getk 4: } k4=4} ' afterrunningthelrualgorithmcache : ' { k1=1，k2=2，k5=5，k6=6，k7=7，k8=8
ajdmj，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰
LFU算法说明：
设计构筑时决定大小的缓存结构，设大小为k，具有以下2个功能。
将set(key，value ) :记录(key，value )插入结构中。 当缓存已满时，它将替换访问频率最低的数据。 get(key ) :返回与key对应的值。 算法实现策略：考虑到LFU将丢弃最不经常访问的数据，需要一种按大小顺序保持数据访问频率的合适方法。 LFU算法本质上可视为选择频率最小的元素的top K问题(K=1)，因此易于认为使用二元堆选择频率最小的元素的实现效率较高。 最终实现方案是在小天花板上堆哈希表。