Skip to content

  • 体验新版
    • 正在加载...
  • 登录
  • KnowledgePlanet
  • docdoc
  • Issue
  • #36

doc
doc
  • 项目概览

KnowledgePlanet / doc

通知 1303
Star 822
Fork 117
  • 代码
    • 文件
    • 提交
    • 分支
    • Tags
    • 贡献者
    • 分支图
    • Diff
  • Issue 42
    • 列表
    • 看板
    • 标记
    • 里程碑
  • 合并请求 0
  • DevOps
    • 流水线
    • 流水线任务
    • 计划
  • Wiki 2
    • Wiki
  • 分析
    • 仓库
    • DevOps
  • 项目成员
  • Pages
doc
doc
  • 项目概览
    • 项目概览
    • 详情
    • 发布
  • 仓库
    • 仓库
    • 文件
    • 提交
    • 分支
    • 标签
    • 贡献者
    • 分支图
    • 比较
  • Issue 42
    • Issue 42
    • 列表
    • 看板
    • 标记
    • 里程碑
  • 合并请求 0
    • 合并请求 0
  • Pages
  • DevOps
    • DevOps
    • 流水线
    • 流水线任务
    • 计划
  • 分析
    • 分析
    • 仓库分析
    • DevOps
  • Wiki 2
    • Wiki
  • 成员
    • 成员
  • 收起侧边栏
  • 动态
  • 分支图
  • 创建新Issue
  • 流水线任务
  • 提交
  • Issue看板
已关闭
开放中
Opened 3月 21, 2024 by 小傅哥@Yao__Shun__Yu⛹Owner

Java实现一个LRU缓存,面试我用TreeMap模拟ZSet做的实现

在Java中,实现一个LRU(Least Recently Used)缓存通常可以通过 LinkedHashMap 来完成,因为它内部维护了元素的插入顺序。但是,如果你想使用 TreeMap 来模拟一个类似 Redis 的 ZSet 结构来实现 LRU 缓存,你可以使用 TreeMap 来根据时间戳排序元素,以此来模拟最近最少使用的缓存淘汰策略。

以下是使用 TreeMap 实现的一个简单的 LRU 缓存的示例代码:

import java.util.Map;
import java.util.TreeMap;

public class LRUCacheWithTreeMap<K, V> {
    private final int capacity;
    private long currentTime = 0L;
    private final Map<K, V> cache;
    private final TreeMap<Long, K> sortedByAccessTime;

    public LRUCacheWithTreeMap(int capacity) {
        this.capacity = capacity;
        this.cache = new TreeMap<>();
        this.sortedByAccessTime = new TreeMap<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        // 更新访问时间
        updateAccessTime(key);
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            // 更新访问时间
            updateAccessTime(key);
        } else {
            if (cache.size() >= capacity) {
                // 缓存已满,移除最久未使用的元素
                evict();
            }
            // 添加新元素
            cache.put(key, value);
            sortedByAccessTime.put(currentTime, key);
        }
    }

    private void updateAccessTime(K key) {
        // 查找并移除旧的访问时间
        for (Map.Entry<Long, K> entry : sortedByAccessTime.entrySet()) {
            if (entry.getValue().equals(key)) {
                sortedByAccessTime.remove(entry.getKey());
                break;
            }
        }
        // 插入新的访问时间
        sortedByAccessTime.put(currentTime++, key);
    }

    private void evict() {
        if (sortedByAccessTime.isEmpty()) {
            return;
        }
        // 移除最久未使用的元素
        Map.Entry<Long, K> oldestEntry = sortedByAccessTime.pollFirstEntry();
        if (oldestEntry != null) {
            cache.remove(oldestEntry.getValue());
        }
    }
}

在这个实现中,我们使用了两个 TreeMap,一个用于存储缓存的键值对,另一个用于按访问时间排序的键。每次访问或添加元素时,我们都会更新访问时间。当缓存达到其容量时,我们会移除最久未使用的元素。

请注意,这个实现并不是线程安全的。如果你需要在多线程环境中使用它,你需要添加适当的同步控制,例如使用 synchronized 关键字或者 ReentrantReadWriteLock。

此外,这个实现的效率并不是特别高,因为每次更新访问时间时都需要遍历 sortedByAccessTime 来查找旧的访问时间。在实际面试中,面试官可能会要求你提供一个更高效的实现,或者解释为什么选择使用 TreeMap 而不是 LinkedHashMap。

指派人
分配到
无
里程碑
无
分配里程碑
工时统计
无
截止日期
无
标识: KnowledgePlanet/doc#36
渝ICP备2023009037号

京公网安备11010502055752号

网络110报警服务 Powered by GitLab CE v13.7
开源知识
Git 入门 Pro Git 电子书 在线学 Git
Markdown 基础入门 IT 技术知识开源图谱
帮助
使用手册 反馈建议 博客
《GitCode 隐私声明》 《GitCode 服务条款》 关于GitCode
Powered by GitLab CE v13.7