LRUCache算法介绍及实现

博主：情天
发布时间：2024 年 07 月 19 日
953 次浏览
2 条评论
2521字数
分类：笔记

# 手写一个简单 LRUCache 缓存淘汰算法

## LRU Cache 算法简介

LRU（Least Recently Used）Cache 算法，即近期最少使用算法，是一种常见的缓存淘汰策略。其核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高；反之，若数据长时间未被访问，则被再次访问的几率也会降低。因此，LRU 算法会优先淘汰那些最近最少使用的数据。

## LRU Cache 实现原理

在 Java 中，LRU 算法的实现通常通过 `LinkedHashMap` 来实现。`LinkedHashMap` 继承自 `HashMap`，它内部使用了一个双向链表来维护元素的顺序。对于 `get`、`put`、`remove` 等操作，`LinkedHashMap` 除了完成 `HashMap` 的基本操作外，还会调整双向链表中元素的顺序。

在 LRU Cache 中，将 `LinkedHashMap` 的顺序设置为 LRU 顺序，即每次访问或插入数据时，都会将该数据移到链表的尾端。这样，当缓存达到最大容量时，链表头部的数据（近期最少使用的数据）会被移除。

## LRU Cache 的实现

以下是一个简单的 LRUCache 实现示例：

```java
static class LRUCache<K, T> implements Iterable {

Integer MAX;
    LinkedHashMap<K, T> cache = new LinkedHashMap();

public LRUCache(Integer MAX) {
        this.MAX = MAX;
    }

public void put(K k, T v) {
        if (cache.containsKey(k)) {
            cache.remove(k);
        } else if (cache.size() >= MAX) {
            cache.remove(cache.keySet().iterator().next());
        }
        cache.put(k, v);
    }

public T get(K k) {
        T t = cache.get(k);
        if (null != t) {
            this.put(k, cache.get(k));
        }
        return t;
    }

@Override
    public Iterator iterator() {

Iterator<Map.Entry<K, T>> iterator = cache.entrySet().iterator();

return new Iterator() {
            @Override
            public boolean hasNext() {
                return iterator.hasNext();
            }

@Override
            public Object next() {
                return iterator.next().getKey();
            }
        };
    }

}
```

### 代码解析

1. **构造函数**

* `LRUCache(Integer MAX)`：构造函数接受一个参数 `MAX`，表示缓存的最大容量。内部使用 `LinkedHashMap` 来存储缓存数据，并通过重写 `removeEldestEntry` 方法来控制缓存的大小。
2. **`put`****方法**

* `public void put(K key, T value)`：将数据放入缓存尾部。如果缓存已满，最早的元素会被自动移除。
3. **`get`****方法**

* `public T get(K key)`：获取缓存中的数据。如果数据存在，则返回该数据；否则返回 `null`。
4. **`iterator`****方法**

* `public Iterator<K> iterator()`：返回缓存中所有键的迭代器。

### 测试代码

在 `main` 方法中，我们创建了一个容量为 5 的 `LRUCache` 对象，并进行了若干次 `put` 和 `get` 操作，最后打印出缓存中的所有键。

```java
public static void main(String[] args) {
    LRUCache<String, String> lruCache = new LRUCache<>(5);

lruCache.put("a", "123");
    lruCache.put("b", "1231");
    lruCache.put("c", "1232");
    lruCache.put("d", "1234");
    lruCache.put("e", "1253");
    lruCache.put("a", "123");
    lruCache.put("e", "1253");

System.out.println("Get key 'cc': " + lruCache.get("cc"));

System.out.print("Current cache keys: ");
    for (String key : lruCache) {
        System.out.print(key + "<-");
    }
}
```

## 结论

本文介绍了 LRU Cache 算法的基本原理，并通过 Java 代码展示了如何使用 `LinkedHashMap` 实现一个简单的 LRU 缓存。通过重写 `LinkedHashMap` 的 `removeEldestEntry` 方法，可以方便地控制缓存的大小，并实现 LRU 缓存策略。在实际应用中，选择合适的缓存算法和数据结构可以显著提升系统性能。

‍

最后修改：2024 年 07 月 19 日