白话 LRU 缓存及链表的数据结构讲解（一）

叁歲伎倆 2022-01-28 07:27 122阅读 0赞

阅读前提：知道缓存（cache）的概念和一定的 Java 数据结构知识。

为了提高性能和减少不必要的重复读取，人们提出了缓存的概念。相对于原本数据的体量，缓存体量非常的少，毕竟我们不可能把所有已经读取的数据都放在缓存里，而且是固定的。这样的话问题就来了，怎么决定哪些数据放在缓存里面，当大小到达上限后，又怎么淘汰（或替换）缓存不需要的数据呢？自然那就是一个策略的问题——通常较简单的做法是使用按照时间排序，把最老的数据删除，把腾空出来的位置让给新来的数据。上述策略有个专业术语：LRU（Least Recently Used，即最近最久未使用的意思）。

接着我们用代码表述 LRU 的意思，假设有 LRUCache 类，它有两个方法 get(key)、set(key, value) ：

// 给出一个限定大小的空间，当前只有两个，演示用
    LRUCache cache = new LRUCache(2);
    
    cache.set(1, 10); // 存入 key 为 1，值为 10
    cache.set(2, 20); // 存入 key 为 2，值为 20
    cache.get(1); // 返回 10，用了一次，更新时间
    cache.set(3, 30); // 虽然插入时间顺序上讲 key 1 最老的，但使用过一次，令 2 变最老的，于是不要 2，存入 key 为 3，值为 30
    cache.get(2); // 返回 -1 找不到
    cache.set(4, 40); // 1 最老的，不要1。存入 key 为 2，值为 20
    cache.get(1); // returns -1 (not found)
    cache.get(3); // returns 30
    cache.get(4); // returns 40

LRU 可谓最“不敬老”的策略，哈哈～看得出 LRU 简单合理，不过又是怎么实现的呢？恐怕却又没那么简单了。首先呢，不管怎么样得有个代表缓存数据的 Node 类，然后多个 Node 元素会存在这个数组里面，——为啥要用数组？其实没啥，一开始嘛，大多数人一般都会想到用简单的数组，我们说那也行，开始就要大家易懂，但是后面会一步一步思考把可行跃进到“很行”。另外，由于要比较出最老的数据，所以自然而然地每一个 Node 数据标记有一个访问的时间戳，于是就有下面的 Node 对象。

class Node { 
        int key; 
        int value; 
        // 记录插入到数组的时间，用于找出最老的数据 
        int timeStamp;  
      
        public Node(int key, int value)   { 
            this.key = key; 
            this.value = value; 
            this.timeStamp = currentTimeStamp;  // 保存系统的时间戳
        } 
    }

插入新数据项（即 set(key, value)）的时候，当数组空间未满，直接插入；当数组空间已满时，将时间戳最大的数据项淘汰，空出的位置给新来的存放。当数据已经存在时候，表明活跃度高，也是令其更新时间戳；每次访问数组中的数据项（即 get(key) 命中）的时候，将被访问的数据项的时间戳设置为最新。

具体实现笔者就不写代码了，网友写有：https://blog.csdn.net/luoweifu/article/details/8297084 。 不过文章里没有使用时间戳来做，而是通过栈的特性实现——这比上述时间戳的方法又进步了一点，通过约定好的空间位置而不是新开辟对象（减少了timeStamp 字段，减少内存）来实现。

一般我们知道，无论操作数组还是栈，对其进行添加插入、删除、移动等的操作还是比较麻烦的，有没有更好的实现办法呢？这里我们引入链表的数据结构，链表的特性就是通过指针来连接元素，维护起来方便。跟前面提到的栈类似，都是利用空间位置来确定最新还是最老的数据。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。链表两端的一头一尾，头是最新的数据，尾是最老的数据。

有些看官可能会问，不懂链表，怎么理解？不打紧，且让笔者一步一步为您介绍，从最简单的单链表（Single Linked List）开始！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3hpbi5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

## 单链表 ##

首先是单链表中的元素对象，表示一个节点。Node next 是指针，指向下一个元素。最后一个元素指向 null，以此为结束的标记。链表两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。

static class Node<T> {
    		Node<T> next;
    		T data;
    
    		public Node(T data) {
    			this.data = data;
    		}
    	}

然后声明对象 LinkedList，有一属性 Node first 表示链表的头部，此结构唯一确定的是头部元素 first；size 是元素总数。当前我们讨论链表，没有指定 size 的上限。

public class LinkedList<T> {
    	public Node<T> first;
    	public int size;
    	.... 对象方法...
    }

接着我们讨论每个方法。第一个是加入新数据到头部的方法。

/**
     * 增加一个节点到链表头部
     */
    public void addFirst(T data) {
    	Node<T> node = new Node<>(data);
    	if (first == null) {
    		first = node;
    	} else {
    		node.next = first; // 下一个是当前头部的
    		first = node;
    	}
    
    	size++;
    }

addFirst() 很好理解，第一步实例化 Node 对象，使其不但有 data 项，还有 next 指针。接着判断当前头部元素是否为空，空的话直接加入，成为第一个元素；若非空，当前头部退居为第二个元素，“让位”给新来的那个元素。在替换 first 之前，要让当前新元素 next 指针指向旧的头部元素，即 node.next = first，然后才 first = node。该方法时间复杂度 O(1)。

/**
     * 增加一个节点到链表尾部
     */
    public void addLast(T data) {
    	if (first == null) {
    		addFirst(data);
    	} else {
    		Node<T> temp = first;
    		while (temp.next != null) {
    			temp = temp.next; // 遍历得到最后一个元素
    		}
    		
    		temp.next = new Node<>(data);
    		size++;
    	}
    }

相对的是加入到尾部。如果没有任何元素，加入到头或尾都是一样。否则，必须得找到最后一个元素，指定 next 指针为新加入的元素。由于有遍历操作，所以该方法时间复杂度为 O(n)。值得一提的是，遍历链表的操作，一般通过 while 循环的写法，如下所示：

Node<T> temp = first;
    	while (temp.next != null) {
    	   .... 具体操作
    		temp = temp.next; // 遍历得到最后一个元素
    	}

接着是查找方法：

/**
     * 查找指定元素
     * 
     * @param data
     * @return
     */
    public T find(T data) {
    	if (size == 0)
    		return null;
    
    	Node<T> temp = first;
    	while (!temp.data.equals(data)) {
    		if (temp.next == null) {// 到达最后，找不到匹配的元素，返回 null
    			return null;
    		} else {
    			temp = temp.next;
    		}
    	}
    
    	return temp.data;
    }

仍然是遍历链表，然而条件有所不同。如果找到返回数据本身，这意义不大；找不到则返回 null。通过该方法，我们又加深了遍历链表的认识。

接着是删除尾部方法：

/**
     * 删除尾部元素
     */
    public void removeLast() {
    	if (size == 0)
    		return;
    
    	Node<T> previous = first; // 要删除元素的话，得先得到该元素的前面一个
    
    	Node<T> temp = first;
    	while (temp.next != null) {
    		previous = temp;
    		temp = temp.next;
    	}
    
    	previous.next = null;
    	size--;
    }

要删除元素的话，得先得到该元素的前面一个元素，便得知 next 为最后一个元素，令其为 null 即可删除。

下面是删除任意元素的方法，该方法稍微复杂一些。

/**
     * 删除指定元素
     */
    public boolean remove(T data) {
    	if (size == 0)
    		return false;
    
    	Node<T> previous = first;
    
    	Node<T> temp = first; // 目标元素
    	while (!temp.data.equals(data)) {
    		if (temp.next == null) { // 到达最后，找不到匹配的元素，返回吧
    			return false;
    		} else {
    			previous = temp;
    			temp = temp.next;
    		}
    	}
    
    	if (temp == first)
    		first = temp.next; // 后面的继续跟着上
    	else
    		previous.next = temp.next; // 删除目标元素就是取前面的元素，然后跳过该元素，让后面的继续跟着上
    
    	size--;
    	
    	return true;
    }

先找出目标元素然后删除之，因此与前面的 find() 有点相似，而且给出前面的那个元素 previous，有何作用？大家看看源码注释，写得很清晰。

至此单链表已经完成，我们可以总结如下图（[图片出处][Link 1]，也是不错的文章！）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3hpbi5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
噢～对了，用法如下：

LinkedList<String> list = new LinkedList<>();
    list.addFirst("1");
    list.addFirst("2");
    list.addFirst("3");
    list.remove("2");
    System.out.println(list.find("3"));
    System.out.println(list);

### 单链表 LRUCache\_1 ###

至今还未跟 LRU 发生联系，只是个普通的单链表。我们在 LinkedList 基础上扩展，反过来说，LRU 可以是单链表的一个特例。

public class LRUCache_1<T> extends LinkedList<T> {
    	int max = 5;
    
    	/**
    	 * 设置最大缓存数量
    	 *
    	 * @param max
    	 */
    	public LRUCache_1(int max) {
    		this.max = max;
    	}
    
    	/**
    	 * 从链表中查询数据， 如果有数据，则将该数据插入链表头部并删除原数据
    	 *
    	 * @param data
    	 * @return
    	 */
    	public T get(T data) {
    		T result = find(data);
    
    		if (result != null) {
    			remove(data);
    			addFirst(data);
    			return result;
    		}
    
    		return null;
    	}
    
    	/**
    	 * 数据在链表中是否存在？ 存在，将其删除，然后插入链表头部 
    	 * 不存在，缓存是否满了？ 满了，删除链表尾结点，将数据插入链表头部 
    	 * 未满，直接将数据插入链表头部
    	 * 时间复杂度O(n)
    	 * 
    	 * @param data
    	 */
    	public void put(T data) {
    		boolean isExist = remove(data);
    		if (isExist) {
    			addFirst(data);
    		} else {
    			if (size < max) {
    				addFirst(data);
    			} else {
    				removeLast();
    				addFirst(data);
    			}
    		}
    	}
    }

原理解释都在代码里面。[代码出处][Link 2] ， 谢谢作者！

## 文末 ##

文章篇幅比较长，先发第一篇。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3hpbi5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220128/e1ad3aca84c046e7b1907d7cba7f25ed.png
[Link 1]: https://www.jianshu.com/p/ac2e242dd73f
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3hpbi5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220128/73ef9deba9474dfd84a1a3e16b986fcf.png
[Link 2]: https://www.jianshu.com/p/4d2b79364941