快捷導(dǎo)航

Java基于LinkedHashMap實現(xiàn)LRU緩存

更新時間：2025年06月03日 10:56:42 作者：喵手

在很多實際的應(yīng)用中,尤其是需要緩存數(shù)據(jù)的場景下,我們經(jīng)常會遇到?LRU緩存,LRU?緩存是通過淘汰最久未使用的緩存數(shù)據(jù)來節(jié)省內(nèi)存空間,在Java中,基于?LinkedHashMap實現(xiàn)LRU緩存是非常簡便和高效的,所以本文介紹了如何基于LinkedHashMap實現(xiàn)LRU緩存,需要的朋友可以參考下

前言

在很多實際的應(yīng)用中，尤其是需要緩存數(shù)據(jù)的場景下，我們經(jīng)常會遇到 LRU（Least Recently Used，最近最少使用）緩存。LRU 緩存是通過淘汰最久未使用的緩存數(shù)據(jù)來節(jié)省內(nèi)存空間。對于高效的 LRU 緩存，我們不僅要保證快速的查找、插入和刪除操作，還要能夠快速地淘汰最久未使用的元素。

在 Java 中，基于 LinkedHashMap 實現(xiàn) LRU 緩存是非常簡便和高效的，因為 LinkedHashMap 本身提供了按照訪問順序迭代的能力，我們可以利用這一特性輕松實現(xiàn) LRU 緩存。

1. LinkedHashMap 簡介

LinkedHashMap 是 HashMap 的一個子類，它基于哈希表實現(xiàn)，并且維護(hù)了插入順序或訪問順序。這使得 LinkedHashMap 特別適合于實現(xiàn)緩存，尤其是在需要按訪問順序迭代時。

1.1 LinkedHashMap 的構(gòu)造方法

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder):
- initialCapacity：初始容量。
- loadFactor：負(fù)載因子。
- accessOrder：如果設(shè)置為 true，則按照訪問順序排序；如果設(shè)置為 false，則按照插入順序排序。

當(dāng) accessOrder 設(shè)置為 true 時，LinkedHashMap 會在每次訪問（get 或 put 操作）時，將訪問的元素移動到鏈表的末尾。這個特性讓我們能夠輕松地實現(xiàn) LRU 緩存。

2. 基于 LinkedHashMap 實現(xiàn) LRU 緩存

2.1 設(shè)計思路

緩存大小限制：我們需要為緩存設(shè)定一個最大容量 capacity，當(dāng)緩存容量超過該值時，我們就需要淘汰最久未使用的元素。
LRU 淘汰規(guī)則：在每次插入或訪問元素時，我們將該元素移動到鏈表的末尾，這樣鏈表的頭部始終保存著最久未使用的元素。當(dāng)緩存容量超過限制時，我們可以直接刪除鏈表頭部的元素。
使用 LinkedHashMap：利用 LinkedHashMap 中 accessOrder 的特性，結(jié)合 removeEldestEntry() 方法來自動刪除最久未使用的元素。

2.2 實現(xiàn)步驟

我們可以創(chuàng)建一個繼承自 LinkedHashMap 的類，并重寫 removeEldestEntry() 方法，該方法會在每次插入新元素時被調(diào)用。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    // 構(gòu)造函數(shù)，初始化容量和 accessOrder
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // 第三個參數(shù) true 表示按訪問順序排序
        this.capacity = capacity;
    }

    // 重寫 removeEldestEntry 方法，當(dāng)緩存容量超出時，移除最久未使用的條目
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    // 獲取緩存中的值
    public V get(K key) {
        return super.getOrDefault(key, null);
    }

    // 插入緩存值
    public void put(K key, V value) {
        super.put(key, value);
    }
}

2.3 代碼說明

LRUCache 類繼承自 LinkedHashMap，并通過構(gòu)造函數(shù)設(shè)置了 accessOrder 為 true，這使得每次訪問元素時，該元素都會被移到鏈表的末尾。
removeEldestEntry() 方法會在每次插入新元素時檢查緩存的大小。如果緩存的大小超過了設(shè)定的容量，它會返回 true，從而自動移除最久未使用的元素。
get(K key) 和 put(K key, V value) 方法分別用于獲取和插入緩存中的數(shù)據(jù)。

2.4 測試案例

public class Main {
    public static void main(String[] args) {
        // 創(chuàng)建一個容量為 3 的 LRU 緩存
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        // 向緩存中插入數(shù)據(jù)
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        // 打印緩存內(nèi)容
        System.out.println(cache); // 輸出: {1=A, 2=B, 3=C}

        // 訪問元素 1
        cache.get(1); // 使元素 1 最近訪問

        // 插入新的元素，此時緩存超過容量，元素 2 將被移除
        cache.put(4, "D");

        // 打印緩存內(nèi)容
        System.out.println(cache); // 輸出: {3=C, 1=A, 4=D}
    }
}

輸出：

{1=A, 2=B, 3=C}
{3=C, 1=A, 4=D}

2.5 解釋

初始時，緩存的容量為 3，元素 {1=A, 2=B, 3=C} 被插入緩存。
當(dāng)訪問 get(1) 時，元素 1 被移動到鏈表的末尾。
當(dāng)插入元素 4=D 時，由于緩存已經(jīng)滿了，元素 2（最久未訪問）被自動刪除，最終緩存內(nèi)容為 {3=C, 1=A, 4=D}。

3. LRU 緩存優(yōu)化

3.1 removeEldestEntry() 方法的靈活性

通過 removeEldestEntry() 方法，我們可以根據(jù)不同的需求定制緩存的淘汰規(guī)則。例如，我們可以根據(jù)某些條件（如元素的大小、元素的過期時間等）來決定是否刪除最久未使用的元素。

3.2 內(nèi)存管理

雖然 LinkedHashMap 的 accessOrder 特性和 removeEldestEntry() 方法讓我們能夠很方便地實現(xiàn) LRU 緩存，但也需要注意緩存大小和內(nèi)存使用的平衡。特別是當(dāng)緩存需要存儲大量數(shù)據(jù)時，合理設(shè)置緩存容量和定期清理緩存非常重要。