LRU的Java实现
发布日期:2021-06-28 19:59:36
浏览次数:2
分类:技术文章
本文共 3607 字,大约阅读时间需要 12 分钟。
文章目录
思路
维护两个数据结构,1个用于“淘汰最远未使用的缓存”,另一个用于“缓存数据查询”
代码实现
import java.util.*;/** lru */class LruCache{ private final int capacity; private final KeyHolder keyHolder; // keyHolder也可以直接使用linkedHashMap。 private final HashMap data; public LruCache(int capacity) { if (capacity < 1) { throw new RuntimeException("capacity can not less than 1"); } this.capacity = capacity; this.keyHolder = new KeyHolder<>(); this.data = new HashMap<>(capacity); } public boolean add(K key, V value) { if (data.size() < capacity || data.containsKey(key)) { this.keyHolder.remove(key); this.keyHolder.add(key); this.data.put(key, value); return true; } else { K key1 = this.keyHolder.poll(); if (key1 != null) { System.out.println("缓存满,删除:" + key1); this.data.remove(key1); } this.keyHolder.add(key); this.data.put(key, value); return true; } } public V get(K key) { V value = this.data.get(key); if (value != null) { this.keyHolder.remove(key); this.keyHolder.add(key); } return value; } public Collection getAll() { return this.data.values(); } public void remove(K key) { this.data.remove(key); this.keyHolder.remove(key); } public static void main(String[] args) { LruCache cache = new LruCache<>(5); cache.add("1", 1); cache.add("2", 2); cache.add("3", 3); cache.add("4", 4); cache.add("5", 5); cache.add("2", 2); cache.add("3", 3); cache.add("1", 1); cache.add("6", 6); cache.add("7", 7); cache.add("8", 8); cache.add("9", 9); cache.add("6", 6); cache.add("7", 7); cache.add("10", 10); cache.add("11", 11); cache.add("12", 12); cache.add("13", 13); cache.add("14", 14); cache.add("1", 1); System.out.println(cache.get("4")); Collection values = cache.getAll(); for (Integer value : values) { System.out.println(value); } } static class Point { Point prev; Point next; K data; } static class KeyHolder { // 双向链表 private Point head; private Point tail; // hash表 private final HashMap > keyHash = new HashMap<>(); /** * 添加一个key * @param key */ void add(K key) { if (keyHash.containsKey(key)) { // key重复,删除后添加 this.remove(key); this.add(key); return; } Point point = new Point (); point.data = key; if (this.tail == null) { // 队列中无数据,初始化 this.head = point; this.tail = point; } else { // 将key添加到尾部 this.tail.next = point; point.prev = this.tail; this.tail = point; } keyHash.put(key, point); } /** * 删除一个key * @param key */ void remove(K key) { Point keyPoint = this.keyHash.get(key); if (keyPoint == null) { // 无key,不删 return; } this.keyHash.remove(key); if (keyPoint.prev == null && keyPoint.next == null) { // 只有这一个节点,将队列设置为空 this.head = null; this.tail = null; } else if (keyPoint.prev == null) { // 这个key是头结点 this.head = keyPoint.next; this.head.prev = null; } else if (keyPoint.next == null) { // 这个key是尾结点 this.tail = keyPoint.prev; this.tail.next = null; } else { keyPoint.prev.next = keyPoint.next; keyPoint.next.prev = keyPoint.prev; } } /** * 从头出一个节点 * @return head */ K poll() { Point keyPoint = this.head; this.keyHash.remove(keyPoint.data); this.head = keyPoint.next; this.head.prev = null; return keyPoint.data; } }}
转载地址:https://blog.csdn.net/xxxxssss12/article/details/107662144 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月10日 14时17分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
CMMI标准名词术语
2019-04-29
CMMI L3学习考核基础试题(测试类)
2019-04-29
Windows Server 2003 sp1升级到sp2报错解决办法
2019-04-29
开源数据库性能测试工具HammerOra介绍
2019-04-29
百Google度搜索
2019-04-29
盛开—痛苦的信仰
2019-04-29
Asp.Net alert弹出提示信息的若干种方法
2019-04-29
Cultrue ‘zh-hans’ is a neutral cultrue报错解决办法
2019-04-29
VS code中关闭eslint
2019-04-29
我的友情链接
2019-04-29
VS code控制台显示乱码解决办法
2019-04-29
删除文件夹操作
2019-04-29
TeamCenter12登陆报404/503问题解决
2019-04-29
Label.text赋值竟然报错“未将对象引用设置到对象的实例”
2019-04-29
TeamCenter12.0升级到12.3过程中ORA-01119: 创建数据库文件失败
2019-04-29
启动Solr提示Java版本低,无法启动的解决办法
2019-04-29
Kafka 集群环境搭建
2019-04-29