java - 在java中删除元素表单链表,意外行为
问题描述
我正在尝试使用 hashmap 和链表在 java 中实现 lru 缓存:
public static class LRUCache{
LinkedList<Integer> ll;
HashMap<Integer, Integer> map;
//HashSet<Integer> map;
int size;
LRUCache(int n){
ll = new LinkedList<>();
map = new HashMap<>();
size=n;
}
int refer(int page){
if(map.containsKey(page)){
Integer it = map.get(page);
//System.out.println("m.get(page)= " + map.get(page));
//System.out.println(it + " it+page " + page);
ll.remove(it);
} else{
if(map.size() >= size){
map.remove(ll.getLast());
ll.removeLast();
}
}
ll.addFirst(page);
//System.out.println(page + " page+peek " + ll.peekFirst());
map.put(page, ll.peekFirst());
return page;
}
}
在上面的引用函数中,对于在地图中找到页面的 if 条件,该值已成功从链接列表中删除,我认为这不应该起作用,因为我只在地图中保留页面值。现在有趣的是,当我把 ll.remove(page); 在上面的代码中,尽管页面和它的值相同,但它会中断。
int refer(int page){
if(map.containsKey(page)){
Integer it = map.get(page);
//System.out.println("m.get(page)= " + map.get(page));
//System.out.println(it + " it+page " + page);
ll.remove(page);
} else{
if(map.size() >= size){
map.remove(ll.getLast());
ll.removeLast();
}
}
ll.addFirst(page);
//System.out.println(page + " page+peek " + ll.peekFirst());
map.put(page, ll.peekFirst());`enter code here`
return page;
}
我对这种行为感到非常惊讶。
对于下面的测试用例,代码的第一个价格有效,第二个无效,唯一的区别是 ll.remove(it) 和 ll.remove(page) ,它和 page 的值是相同的。
void printCache(){
System.out.print("| ");
for(int i=0;i<ll.size();i++){
System.out.print(ll.get(i) + " |" + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(4);
lruCache.refer(11);
lruCache.refer(12);
lruCache.refer(13);
lruCache.printCache();
lruCache.refer(11);
lruCache.printCache();
lruCache.refer(14);
lruCache.printCache();
lruCache.refer(13);
lruCache.printCache();
lruCache.refer(15);
lruCache.printCache();
}
解决方案
保留两个集合对于缓存来说是昂贵的,为什么不使用单个集合。Linkedhashmap 保持插入顺序。此外,您必须牢记并发性。也许两个同时命中会使您丢失数据。只需使用 Collections.synchronizedMap 包装地图。Linkedhashmap 可以保留长类型的密钥。您可以将时间(以毫秒为单位)作为键。然后您可以通过键搜索找到最后使用的元素,或者只是简单地删除最后插入的元素。
推荐阅读
- ms-word - 动态显示文本 MS Word 邮件合并
- django - 创建配置文件编辑视图
- sprite-kit - UIPanGestureRecognizer 未按预期运行
- pandas - 有效地使用混合类型更改数据帧值 dtype
- firebase - 用于在用户对用户聊天中存储数千条消息的 Firestore?
- reactjs - 终止/重新启动 React 应用程序的选项有哪些?
- java - 使用 REST 模板进行 Spock E2E 测试
- dart - 这些函数返回值在 Dart 中是如何工作的?
- authentication - 未定义属性:Illuminate\Auth\AuthManager
- mysql - 日期时间字段上的 MySQL 索引不是 RANGE 类型,而是使用 INDEX 类型