共计 2430 个字符,预计需要花费 7 分钟才能阅读完成。
前言
最近在逛博客的时候看到了无关 Redis 方面的面试题,其中提到了 Redis 在内存达到最大限度的时候会应用 LRU 等淘汰机制,而后找了这方面的一些材料与大家分享一下。
LRU 总体大略是这样的,最近应用的放在后面,最近没用的放在前面,如果来了一个新的数,此时内存满了,就须要把旧的数淘汰,那为了不便挪动数据,必定就得应用链表相似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要应用 hashmap 等 key-value 模式的数据结构。
第一种实现 (应用 LinkedHashMap)
public class LRUCache {
int capacity;
Map<Integer,Integer> map;
public LRUCache(int capacity){
this.capacity = capacity;
map = new LinkedHashMap<>();}
public int get(int key){
// 如果没有找到
if (!map.containsKey(key)){return -1;}
// 找到了就刷新数据
Integer value = map.remove(key);
map.put(key,value);
return value;
}
public void put(int key,int value){if (map.containsKey(key)){map.remove(key);
map.put(key,value);
return;
}
map.put(key,value);
// 超出 capacity,删除最久没用的即第一个, 或者能够复写 removeEldestEntry 办法
if (map.size() > capacity){map.remove(map.entrySet().iterator().next().getKey());
}
}
public static void main(String[] args) {LRUCache lruCache = new LRUCache(10);
for (int i = 0; i < 10; i++) {lruCache.map.put(i,i);
System.out.println(lruCache.map.size());
}
System.out.println(lruCache.map);
lruCache.put(10,200);
System.out.println(lruCache.map);
}
第二种实现 (双链表 +hashmap)
public class LRUCache {
private int capacity;
private Map<Integer,ListNode>map;
private ListNode head;
private ListNode tail;
public LRUCache2(int capacity){
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode(-1,-1);
tail = new ListNode(-1,-1);
head.next = tail;
tail.pre = head;
}
public int get(int key){if (!map.containsKey(key)){return -1;}
ListNode node = map.get(key);
node.pre.next = node.next;
node.next.pre = node.pre;
return node.val;
}
public void put(int key,int value){if (get(key)!=-1){map.get(key).val = value;
return;
}
ListNode node = new ListNode(key,value);
map.put(key,node);
moveToTail(node);
if (map.size() > capacity){map.remove(head.next.key);
head.next = head.next.next;
head.next.pre = head;
}
}
// 把节点挪动到尾巴
private void moveToTail(ListNode node) {
node.pre = tail.pre;
tail.pre = node;
node.pre.next = node;
node.next = tail;
}
// 定义双向链表节点
private class ListNode{
int key;
int val;
ListNode pre;
ListNode next;
// 初始化双向链表
public ListNode(int key,int val){
this.key = key;
this.val = val;
pre = null;
next = null;
}
}
}
像第一种形式,如果复写 removeEldestEntry 会更简略,这里简略的展现一下
public class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;
}
}
原文链接:https://blog.csdn.net/Grady00…
版权申明:本文为 CSDN 博主「拉霍拉卡」的原创文章,遵循 CC 4.0 BY-SA 版权协定,转载请附上原文出处链接及本申明。
近期热文举荐:
1.600+ 道 Java 面试题及答案整顿 (2021 最新版)
2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了,真香!
3. 阿里 Mock 工具正式开源,干掉市面上所有 Mock 工具!
4.Spring Cloud 2020.0.0 正式公布,全新颠覆性版本!
5.《Java 开发手册(嵩山版)》最新公布,速速下载!
感觉不错,别忘了顺手点赞 + 转发哦!