如何利用 LinkedHashMap 快速实现一个简易的 LRU（最近最少使用）缓存淘汰组件？

知识点图片

我来为你详细介绍如何使用 LinkedHashMap 快速实现 LRU 缓存淘汰组件。

核心原理

LinkedHashMap 提供了两种访问顺序模式：

插入顺序：默认模式，按元素插入顺序排列
访问顺序：通过构造函数设置 accessOrder = true，按访问顺序排列（包括 get/put 操作）

基础实现

java

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

public class LRUCache<K, V> {
    private final LinkedHashMap<K, V> cache;
    private final int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // accessOrder = true 表示按访问顺序排序
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                // 当 size() > capacity 时自动移除最久未使用的元素
                return size() > LRUCache.this.capacity;
            }
        };
    }
    
    public synchronized V get(K key) {
        return cache.getOrDefault(key, null);
    }
    
    public synchronized void put(K key, V value) {
        cache.put(key, value);
    }
    
    public synchronized int size() {
        return cache.size();
    }
    
    public synchronized void clear() {
        cache.clear();
    }
}

完整功能版本

java

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class AdvancedLRUCache<K, V> {
    private final LinkedHashMap<K, V> cache;
    private final int capacity;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    
    public AdvancedLRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be positive");
        }
        
        this.capacity = capacity;
        
        // initialCapacity: 初始容量，loadFactor: 负载因子，accessOrder: true=访问顺序排序
        this.cache = new LinkedHashMap<K, V>(
            (int)(capacity / 0.75f + 1), // initialCapacity ≈ capacity / loadFactor + safety margin  
            0.75f,
            true) { 
            
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > AdvancedLRUCache.this.capacity;
            }
            
            @Override 
            public String toString() {
                return "LRU Cache: " + super.toString();  
            }  
        };
        
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

}

ThreadSafeLRUCache.java

java


public class ThreadSafeLRUCache {

}

Usage Example

java


class Main {

}

Key Points Explained

Constructor Parameters:

initialCapacity: (int)(capacity / loadFactor + 1) - Prevents rehashing when reaching full capacity.
loadFactor: 0.75f - Default HashMap/LinkedListMap load factor balancing space/time efficiency.
accessOrder: true - Enables access-order sorting instead of insertion order.

removeEldestEntry Method:

This method is called after each put operation and determines whether to evict the eldest entry based on your custom logic — in our case we check if current size exceeds max allowed limit (size() > this.capacity). If it returns true, then that eldest entry will be removed automatically by LinkedHashSet implementation itself before returning from calling method such as put().

By overriding this hook function inside anonymous subclass definition we can easily implement various eviction policies like LFU (Least Frequently Used), FIFO etc., just modifying condition accordingly!

右滑查看面试常问

播面