单链表实现LRU缓存淘汰算法
- 2020 年 2 月 10 日
- 筆記
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高，相反如果很长时间未被访问，则它在最近一段时间内也不会被访问。实现方式有很多种，这里先介绍基于数组和单链表的实现方式。
基于数组的LRU
首位置保存最新访问数据，末尾位置优先清理。
- 如果此数据之前已经被缓存在数组中了，查找到其位置并从原位置中删除该数据，将位置之前的数据依次右移一位，保存此数据到数组第一个元素位置上。
- 如果此数据没有在缓存数组中，又可以分为两种情况：
- 如果此时缓存未满，将数组中数据全部右移一位，保存此数据到数组第一个元素位置上。
- 如果此时缓存已满，将数组最后一位数据删除，再将数组中数据全部右移一位，保存此数据到数组第一个元素位置上。
public class LRUBasedArray<T> { private final int DEFAUL_CAPACITY = 10; private Integer capacity; private Integer count; private T[] value; /** * 用于元素记录所在数组位置 */ private Map<T, Integer> holder; public LRUBasedArray() { this.capacity = this.DEFAUL_CAPACITY; this.value = (T[]) new Object[capacity]; this.count = 0; this.holder = new HashMap<T, Integer>(capacity); } public LRUBasedArray(Integer capacity) { this.capacity = capacity; this.value = (T[]) new Object[capacity]; this.count = 0; this.holder = new HashMap<T, Integer>(capacity); } /** * 缓存数据 * @param data */ public void add(T data){ if (data == null){ throw new IllegalArgumentException("该缓存容器不支持null!"); } Integer index = holder.get(data); if (index != null){ // 向右移动 update(index); }else { // 是否已满 if (isFull()){ // 删除，更新 removeAndCache(data); }else { // 右移元素更新 cache(data, count); } } } /** * 数据之前已在数组中，将数组中的对应数据更新到数组开始。 * @param index */ private void update(Integer index){ T key = value[index]; rightOffer(index); value[0] = key; holder.put(key,0); } /** * 向数组插入新数据 * @param data * @param end */ private void cache(T data, Integer end){ rightOffer(end); value[0] = data; holder.put(data,0); count++; } /** * 删数组最后一位，并将新数据保存到数组开始 * @param data */ private void removeAndCache(T data){ T key = value[--count]; holder.remove(key); cache(data, count); } /** * index左侧的统一向右移动一位 * @param index */ private void rightOffer(Integer index){ for (int i=index;i>0;i--){ value[i] = value[i-1]; holder.put(value[i],i); } } /** * 判断数组是否已满 * @return */ private boolean isFull(){ return count == capacity; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < count; i++) { sb.append(value[i]); sb.append(" "); } return sb.toString(); } public static void main(String[] args) { LRUBasedArray<Integer> array = new LRUBasedArray(); Random random = new Random(20); int num = 0; for (int i=0;i<20;i++){ num = random.nextInt(20); array.add(num); PrintUtill.println("插入"+ num + ":"); PrintUtill.println(array.toString()); } } }
当然也可以首位置优先清理，末尾位置保存最新访问数据，思想类似，这里就不再赘述。
基于单链表
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部；
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
public class LRUBaseLinkedList<T> { /** * 默认容量 */ private final int DEFAUL_CAPACITY = 10; /** * 头结点 */ private SNode<T> head; /** * 链表长度 */ private Integer length; /** * 链表容量 */ private Integer capacipy; public LRUBaseLinkedList() { this.head = new SNode<>(); this.length = 0; this.capacipy = DEFAUL_CAPACITY; } public LRUBaseLinkedList(Integer capacipy) { this.head = new SNode<>(); this.length = 0; this.capacipy = capacipy; } /** * 缓存数据 * @param data */ public void add(T data){ SNode preNode = findPreNode(data); if (preNode != null){ // 删除节点 deleteElemOptim(preNode); }else { // 节点不存在，队列是否已满 if (length>=capacipy){ // 已满，删除队尾 deleteElemAtEnd(); } } // 将节点插入到头 intsertElemAtBegin(data); } /** * 删除某个结点 * @param node */ public void deleteElemOptim(SNode node){ node.setNext(node.getNext().getNext()); length--; } /** * 删除链表尾部的结点 */ public void deleteElemAtEnd(){ SNode node = head; if (node.getNext() == null) return; while (node.getNext().getNext() != null){ node = node.getNext(); } node.getNext().setNext(null); length--; } /** * 在头部插入结点 * @param data */ public void intsertElemAtBegin(T data){ SNode node = new SNode(data, head.getNext()); head.setNext(node); length++; } /** * 获取查找到元素的前一个节点 * @param data * @return */ private SNode findPreNode(T data){ SNode node = head; while (node.getNext() != null){ if (node.getNext().element.equals(data)){ return node; } node = node.getNext(); } return null; } private void printAll(){ SNode node = head.getNext(); while (node!=null){ PrintUtill.print(node.element+">"); node = node.getNext(); } PrintUtill.printlnRule(); } public class SNode<T> { private T element; private SNode next; public SNode() { this.next = null; } public SNode(T element, SNode next) { this.element = element; this.next = next; } public T getElement() { return element; } public void setElement(T element) { this.element = element; } public SNode getNext() { return next; } public void setNext(SNode next) { this.next = next; } } public static void main(String[] args) { LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<Integer>(); Random random = new Random(20); int num = 0; for (int i=0;i<20;i++){ num = random.nextInt(20); list.add(num); PrintUtill.println("插入"+ num + ":"); list.printAll(); } } }
延伸
什么是缓存
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。
有哪些缓存淘汰策略？
常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
什么是链表
- 和数组一样是一种线性表。
- 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
- 链表中的每一个内存块被称为结点Node。结点除了存储数据外，还需记录链上的下一个结点的地址，即后继指针next。
常用链表
单链表、循环链表、双向链表、双向循环链表
单链表
- 每个结点只包含一个指针，即后继指针。
- 单链表有两个特殊结点，即头结点和尾结点。头结点用来记录链表的基地址，可以遍历得到整条链表。尾结点指向一个空地址 NULL，表示这是链表上最后一个结点。
- 插入和删除结点的时间复杂度为O（1），查找的时间复杂度为O(n)。
循环链表
一种特殊的单链表。
- 它跟单链表唯一的区别是尾结点指针是指向链表的头结点。
- 循环链表的优点是从链尾到链头比较方便。适用于处理具有环型结构特点的数据，比如著名的约瑟夫问题。
双向链表
- 结点除了存储数据外，还有两个指针分别指向前一个结点地址（前驱指针prev）和下一个结点地址（后继指针next）。
- 头结点的前驱指向为空，尾结点指向为空。
- 给定数据值查询/删除对应结点，双向和单链表的时间复杂度均是O(n)；给定结点的查询/删除，双向O(1)，单链表O(n)。
双向循环链表
首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。
用空间换时间的设计思想
对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化。 消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。
数组和链表比较：
- 链表插入、删除数据效率高，时间复杂度O(1)，随机访问效率低，时间复杂度O(n)。
- 数组插入、删除数据效率低，时间复杂度O(n)，随机访问效率高，时间复杂度O(1)。
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
链表本身没有大小的限制，天然地支持动态扩容。
如果代码对内存的使用非常苛刻，那数组就更适合。
数组缺点
内存中没有足够的连续空间时，数组申请空间会失败，导致内存不足(out of memory)。
数组大小固定，当不够用时，需要扩容，一旦扩容就要进行数据复制，而这时非常费时。
链表缺点
内存消耗大，因为要消耗额外的空间存储指针信息。
对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片。Java语言中还可能会造成频繁的GC（Garbage Collection，垃圾回收）。
