Java面试必知：LRU缓存原理与实现详解

一、LRU缓存简介

LRU（Least Recently Used）缓存算法是一种常用的缓存淘汰策略，它根据数据的使用频率来淘汰缓存中的数据。LRU缓存算法遵循一个原则：当缓存满时，优先淘汰最久未被使用的数据。这种算法在Java面试中经常被问到，因此掌握LRU缓存原理与实现对于Java开发者来说至关重要。

二、LRU缓存原理

LRU缓存算法的核心思想是：当缓存满时，先淘汰最久未被使用的数据。具体实现如下：

1. 使用双向链表存储缓存数据，链表头表示最近使用的数据，链表尾表示最久未被使用的数据。

2. 当访问缓存数据时，将该数据移动到链表头部，表示该数据最近被使用过。

3. 当缓存满时，淘汰链表尾部的数据。

4. 当添加新数据时，如果缓存未满，直接添加到链表头部；如果缓存已满，则淘汰链表尾部的数据，并将新数据添加到链表头部。

三、Java实现LRU缓存

在Java中，我们可以使用HashMap和LinkedList来实现LRU缓存。下面是LRU缓存的实现代码：

```java

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

public class LRUCache {

private int capacity; // 缓存容量

private Map> map; // 存储缓存数据

private LinkedList> list; // 双向链表存储缓存数据

public LRUCache(int capacity) {

this.capacity = capacity;

this.map = new HashMap<>();

this.list = new LinkedList<>();

}

public V get(K key) {

Node node = map.get(key);

if (node == null) {

return null;

}

moveToHead(node);

return node.value;

}

public void put(K key, V value) {

Node node = map.get(key);

if (node == null) {

Node newNode = new Node<>(key, value);

map.put(key, newNode);

list.addFirst(newNode);

if (list.size() > capacity) {

Node tail = list.removeLast();

map.remove(tail.key);

}

} else {

node.value = value;

moveToHead(node);

}

}

private void moveToHead(Node node) {

list.remove(node);

list.addFirst(node);

}

private static class Node {

K key;

V value;

Node prev;

Node next;

Node(K key, V value) {

this.key = key;

this.value = value;

}

}

}

```

四、LRU缓存的应用场景

LRU缓存算法在Java开发中有着广泛的应用场景，以下列举几个常见的应用场景：

1. 数据库查询缓存：缓存最近查询过的数据，提高查询效率。

2. 页面缓存：缓存最近访问过的页面，减少服务器压力。

3. 图片缓存：缓存最近访问过的图片，提高页面加载速度。

4. 应用程序缓存：缓存应用程序中频繁使用的数据，提高应用程序性能。

五、总结

LRU缓存算法是一种常用的缓存淘汰策略，在Java面试中经常被问到。本文详细介绍了LRU缓存原理与实现，并通过Java代码展示了如何使用HashMap和LinkedList实现LRU缓存。掌握LRU缓存原理与实现对于Java开发者来说至关重要，希望本文能对大家有所帮助。