招商银行（深圳），复盘，一面算法

算法：
java中的缓存你是用哪些实现的？内存缓存？LRU算法淘汰机制？用java中的什么数据结构实现？

设计一个简单的缓存的一个淘汰机制，比如说我举个例子，这个缓存只允许上限为十个，超出十个之后，你就要有一个淘汰机制策略？把老的剔除出去？

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

/**
 * 简单LRU缓存（上限10个元素，满时淘汰最近最少使用的数据）
 * @param <K> 缓存键类型
 * @param <V> 缓存值类型
 */
public class SimpleLRUCache<K, V> {
    // 缓存底层存储：LinkedHashMap，开启“按访问顺序排序”
    private final LinkedHashMap<K, V> cacheMap;
    // 缓存最大容量（题目要求10）
    private final int MAX_CAPACITY = 10;

    // 构造函数：初始化LinkedHashMap，开启访问顺序排序
    public SimpleLRUCache() {
        // 参数说明：
        // 1. initialCapacity：初始容量（设为10，和最大容量一致，避免扩容）
        // 2. loadFactor：负载因子（0.75是默认最优值，避免频繁扩容）
        // 3. accessOrder：true=按访问顺序排序，false=按插入顺序排序（LRU必须设为true）
        cacheMap = new LinkedHashMap<>(MAX_CAPACITY, 0.75f, true) {
            // 重写此方法：判断是否需要删除最老元素
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                // 当缓存size > 最大容量时，返回true，自动删除最老元素（eldest就是最老的）
                return size() > MAX_CAPACITY;
            }
        };
    }

    // 1. 存缓存：key不存在则新增，存在则更新值（更新后会自动移到链表尾部，标记为“最近使用”）
    public void put(K key, V value) {
        cacheMap.put(key, value);
    }

    // 2. 取缓存：获取值的同时，会自动把该元素移到链表尾部（标记为“最近使用”）
    public V get(K key) {
        return cacheMap.get(key); // 若key不存在，返回null
    }

    // 3. 删缓存：手动删除指定key的缓存
    public void remove(K key) {
        cacheMap.remove(key);
    }

    // 4. 辅助方法：查看当前缓存所有数据（用于测试，看淘汰效果）
    public void printCache() {
        System.out.println("当前缓存数据（顺序：从左到右是“最久未使用”到“最近使用”）：");
        for (Map.Entry<K, V> entry : cacheMap.entrySet()) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + " ");
        }
        System.out.println("\n当前缓存大小：" + cacheMap.size());
    }

    // 测试：验证LRU淘汰效果
    public static void main(String[] args) {
        SimpleLRUCache<Integer, String> cache = new SimpleLRUCache<>();

        // 1. 先存10个元素（达到最大容量）
        for (int i = 1; i <= 10; i++) {
            cache.put(i, "value" + i);
        }
        System.out.println("=== 存满10个元素后 ===");
        cache.printCache(); // 输出：1=value1 2=value2 ... 10=value10（1是最老，10是最新）

        // 2. 访问第3个元素（标记为“最近使用”，会移到尾部）
        cache.get(3);
        System.out.println("\n=== 访问key=3后 ===");
        cache.printCache(); // 输出：1=value1 2=value2 4=value4 ... 3=value3（3移到尾部）

        // 3. 再存第11个元素（触发淘汰，删除最老的key=1）
        cache.put(11, "value11");
        System.out.println("\n=== 存第11个元素后（触发淘汰） ===");
        cache.printCache(); // 输出：2=value2 4=value4 ... 11=value11（key=1被淘汰，size保持10）
    }
}

// 伪码：手动实现LRU缓存（上限10）
class SimpleLRUCache {
    // 缓存实体：存key、value、最后访问时间戳
    class CacheItem {
        K key;
        V value;
        long lastAccessTime; // 毫秒级时间戳，记录最后访问时间
    }

    CacheItem[] cacheArray; // 存储缓存的数组（大小10）
    int currentSize; // 当前缓存元素个数

    // 初始化：数组大小10，currentSize=0
    function SimpleLRUCache() {
        cacheArray = new CacheItem[10];
        currentSize = 0;
    }

    // 存缓存
    function put(K key, V value) {
        1. 检查key是否已存在：
           - 若存在：更新对应value，同时更新lastAccessTime为当前时间；
           - 若不存在：
               a. 若currentSize < 10：直接把新CacheItem放入数组，currentSize+1；
               b. 若currentSize == 10：找出数组中lastAccessTime最小的元素（最久未使用），替换成新CacheItem；
    }

    // 取缓存
    function get(K key) {
        1. 遍历数组找对应key：
           - 若找到：更新其lastAccessTime为当前时间，返回value；
           - 若没找到：返回null；
    }

    // 淘汰逻辑：在put满10个时，调用此方法找最久未使用元素
    function findOldestItem() {
        1. 遍历数组，记录lastAccessTime最小的元素索引；
        2. 返回该元素索引，用于后续替换；
    }
}