基於 Java 實現 LRU 快取：LinkedHashMap 實戰解析

LRU（Least Recently Used，最近最少使用）是一種經典的快取淘汰策略。Java 中利用 LinkedHashMap 的存取順序特性，可以輕鬆實現一個高效的 LRU 快取。本文提供完整原始碼並解析核心邏輯。

核心原理

LinkedHashMap 繼承自 HashMap，並維護一條雙向鏈表。當以 accessOrder = true 建立實例時，每次呼叫 get 或 put 會將對應節點移至鏈表尾部。重寫 removeEldestEntry 方法，在大小超過上限時移除鏈表頭部（最久未使用）的節點，即可實現 LRU。

完整實現程式碼

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

public class LRUCache {

    public static class CachedData {
        private Object data = null;
        private long time = 0;
        private boolean refreshing = false;

        public CachedData(Object data) {
            this.data = data;
            this.time = System.currentTimeMillis();
        }

        public Object getData() { return data; }
        public long getTime() { return time; }
        public void setTime(long time) { this.time = time; }
        public boolean getRefreshing() { return refreshing; }
        public void setRefreshing(boolean b) { this.refreshing = b; }
    }

    protected static class CacheMap extends LinkedHashMap {
        protected int maxsize = 0;

        public CacheMap(int maxsize) {
            super(maxsize * 4 / 3 + 1, 0.75f, true); // accessOrder = true
            this.maxsize = maxsize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > this.maxsize;
        }
    }

    protected CacheMap map = null;

    public LRUCache(int size) {
        this.map = new CacheMap(size);
    }

    public synchronized void set(Object key, Object value) {
        map.remove(key);
        map.put(key, new CachedData(value));
    }

    public synchronized void remove(Object key) {
        map.remove(key);
    }

    public synchronized CachedData get(Object key) {
        CachedData value = (CachedData) map.get(key);
        if (value == null) return null;
        // 移動到尾部，標記為最近使用
        map.remove(key);
        map.put(key, value);
        return value;
    }

    public int usage() { return map.size(); }
    public int capacity() { return map.maxsize; }
    public void clear() { map.clear(); }
}

關鍵點說明

• 同步控制：公開方法均加上 synchronized，保證執行緒安全。
• 快取元資料：CachedData 封裝資料本體、時間戳與刷新狀態，支援進階策略（如定時失效）。
• 容量計算：建構子傳入 maxsize * 4 / 3 + 1 作為初始容量，配合負載因子 0.75，減少擴容頻率。

此實現簡潔高效，適合作為輕量級記憶體快取元件直接整合至專案中。