Java面试必考：LRU缓存原理与实现，轻松应对面试难题

LRU（Least Recently Used）缓存算法是一种常用的缓存淘汰策略，它根据数据的历史访问记录来淘汰最久未使用的缓存数据。在Java面试中，LRU缓存算法是一个高频考点，本文将深入解析LRU缓存原理，并给出Java实现方案，帮助你在面试中轻松应对。

一、LRU缓存原理

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

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

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

3. 当缓存满时，淘汰链表尾部的数据，即最久未使用的数据。

二、Java实现LRU缓存

下面是使用Java实现LRU缓存的示例代码：

```java

import java.util.HashMap;

import java.util.Map;

public class LRUCache {

private final int capacity; // 缓存容量

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

private final Node head; // 链表头

private final Node tail; // 链表尾

public LRUCache(int capacity) {

this.capacity = capacity;

this.map = new HashMap<>();

this.head = new Node<>(null, null);

this.tail = new Node<>(null, null);

head.next = tail;

tail.prev = head;

}

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);

addNode(newNode);

if (map.size() > capacity) {

Node tailNode = removeTail();

map.remove(tailNode.key);

}

} else {

node.value = value;

moveToHead(node);

}

}

private void moveToHead(Node node) {

removeNode(node);

addNode(node);

}

private void addNode(Node node) {

node.next = head.next;

node.prev = head;

head.next.prev = node;

head.next = node;

}

private void removeNode(Node node) {

node.prev.next = node.next;

node.next.prev = node.prev;

}

private Node removeTail() {

Node tailNode = tail.prev;

removeNode(tailNode);

return tailNode;

}

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. HTTP缓存：缓存HTTP请求结果，减少网络传输时间，提高页面加载速度。

3. 缓存热点数据：缓存频繁访问的数据，如用户信息、商品信息等，减少数据库访问压力。

4. 缓存分布式系统中的数据：缓存分布式系统中的热点数据，提高系统整体性能。

四、总结

LRU缓存算法是一种简单而有效的缓存淘汰策略，在Java面试中经常被考察。本文详细解析了LRU缓存原理，并给出了Java实现方案，希望对你有所帮助。在实际开发中，合理运用LRU缓存算法，可以提高系统性能，降低资源消耗。