LRU缓存替换策略与C语言实现有何关联？

本文共计3184个文字，预计阅读时间需要13分钟。

目录 + LRU缓存替换策略 + 核心思想 + 不适用场景 + 算法基本实现 + 算法优化 + 优化思路： + 进一步优化 + Benchmark + LRU缓存替换策略 + 缓存是一种常见设计，通过将数据存储到访问速度更快的存储介质中，提高访问速度

目录

• LRU缓存替换策略
• 核心思想
• 不适用场景
• 算法基本实现
• 算法优化
• 优化思路：
• 进一步优化
• Benchmark

LRU缓存替换策略

缓存是一种非常常见的设计，通过将数据缓存到访问速度更快的存储设备中，来提高数据的访问速度，如内存、CPU缓存、硬盘缓存等。

但与缓存的高速相对的是，缓存的成本较高，因此容量往往是有限的，当缓存满了之后，就需要一种策略来决定将哪些数据移除出缓存，以腾出空间来存储新的数据。

这样的策略被称为缓存替换策略（Cache Replacement Policy）。

常见的缓存替换策略有：FIFO（First In First Out）、LRU（Least Recently Used）、LFU（Least Frequently Used）等。

今天给大家介绍的是LRU算法。

核心思想

LRU算法基于这样一个假设：如果数据最近被访问过，那么将来被访问的几率也更高。

大部分情况下这个假设是成立的，因此LRU算法也是比较常用的缓存替换策略。