Java基于LinkedHashMap實現LRU緩存

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

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

前言

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

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

1. LinkedHashMap 簡介

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

1.1 LinkedHashMap 的構造方法

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

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

2. 基于 LinkedHashMap 實現 LRU 緩存

2.1 設計思路

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

2.2 實現步驟

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

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

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

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

    // 重寫 removeEldestEntry 方法，當緩存容量超出時，移除最久未使用的條目
    @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，并通過構造函數設置了 accessOrder 為 true，這使得每次訪問元素時，該元素都會被移到鏈表的末尾。
removeEldestEntry() 方法會在每次插入新元素時檢查緩存的大小。如果緩存的大小超過了設定的容量，它會返回 true，從而自動移除最久未使用的元素。
get(K key) 和 put(K key, V value) 方法分別用于獲取和插入緩存中的數據。

2.4 測試案例

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

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

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

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

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

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

輸出：