链表：如何实现LRU缓存淘汰算法?
缓存淘汰策略：
FIFO:先入先出策略
LFU：最少使用策略
LRU：最近最少使用策略
链表的数据结构：
可以看到，数组需要连续的内存空间，当内存空间充足但不连续时，也会申请失败触发GC，链表则可以是零散的。
常见的链表结构有：单链表，双向链表，循环链表等。
以单链表为例
每个节点除了存储数据以外，还要存储下一个节点地址，我们称之为后继指针。
头结点记录链表的基地址，尾节点的后继指针指向的是空地址null
循环链表：
双向链表：
双向循环链表：
双向链表插入，删除操作的时间复杂度是O(1)
单链表插入，删除操作的时间复杂度是O(n)
链表随机访问的时间复杂度是O(n)
注意：
单纯删除的时间复杂度是O(1)，但往往删除前需要根据下标查找，时间复杂度为O(n)
针对删除操作与插入操作，由于单链表没有记录前驱节点位置，所以在删除与插入时，需要重新遍历链表，而双向链表则不需要。
java语言中，LinkedHashMap使用的就是双向链表。双向链表虽然比较耗费内存空间，但是性能更好，这是一种空间换时间的设计思想。
数组与链表各有利弊，数组对于缓存十分友好，且简单易用，缺点是数组是定长的，而容器如ArrayList，虽然支持动态扩容，但在扩容的时候需要重新分配空间且拷贝数据，十分损耗性能与内存。链表则会损耗更多的内存空间，并且会造成内存碎片，在java语言中，使用不当可能导致频繁的GC。
实际使用过程，应当根据场景选择使用数组还是链表。
使用链表实现LRU缓存淘汰算法：
使用单向链表存储缓存数据
缓存读取一个数据以后，遍历单向链表，有两种情况：
1.链表中已经存在，删除该数据，并且存储在链表头部
2.链表中不存在，又分为两种情况
链表未满，直接插入到链表头部
链表已满，删除尾部数据，将该数据存在链表头部
“数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。” 这里的CPU缓存机制指的是什么？为什么就数组更好了？
CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(这个大小我不太确定)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。
Cache Line 是 Cache 与 DRAM 同步的最小单位. 典型的虚拟内存页面大小为 4KB,而典型的 Cache line 通常的大小为 32 或 64 字节
优质内容筛选与推荐>>
1、java包分类包括java.*,sun.*
2、【目标检测】SSD目标检测
3、Android双进程Service常驻后台，无惧“一键清理”
4、这个微信里的「稍后阅读」，帮你一键收集好文章
5、spark连接kafka工具类
1、java包分类包括java.*,sun.*
2、【目标检测】SSD目标检测
3、Android双进程Service常驻后台，无惧“一键清理”
4、这个微信里的「稍后阅读」，帮你一键收集好文章
5、spark连接kafka工具类