1. 什么是LRU缓存淘汰
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
2. 缓存的意义
我们都知道，缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
3. 缓存淘汰策略有哪些？
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
4. 为什么是链表实现而不是数组？
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。
数组和链表的内存分布.png
5. 常用的链表有哪些？
常用的链表有：单链表、循环链表和双向链表。
-
我们首先来看最简单、最常用的单链表。
单链表.png
头节点记录了链表的基地址，尾节点指向NULL。只要知道链表的头结点信息，就可以遍历整个链表。
- 循环链表，一种特殊的单链表
循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。
image.png
- 双向链表
image.png
5. LRU缓存算法实现思路
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
6. 存在的问题
每次都去遍历链表，时间复杂度为O(n)。
散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。
7. 什么是散列表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
8. 小结
熟悉了各种数据结构，才能信手拈来，根据不同的场景，使用不同的数据结构。这也是我现在学习的目标，每次总结下自己学到的东西。
网友评论