LRU、LFU缓存机制的算法设计与实现

文章目录

LRU缓存机制 LFU缓存机制 其他缓存机制 FIFO缓存机制 OPT缓存机制 LRU算法设计与实现 LFU算法设计与实现

缓存算法和内存页面置换算法（Page Replacement Algorithm）的核心思想是一样的：给定一个有限的空间，设计一个算法来更新和访问里面的数据。下面提到缓存算法的同时，也指代页面置换算法。

LRU缓存机制

LRU（The Least Recently Used，最近最久未使用算法） 是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。