浅谈java如何实现Redis的LRU缓存机制
短信预约 -IT技能 免费直播动态提醒
LRU概述
最近使用的放在前面,最近没用的放在后面,如果来了一个新的数,此时内存满了,就需要把旧的数淘汰,那为了方便移动数据,肯定就得使用链表类似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构。
使用LinkedHashMap实现
package thread;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCacheTest {
int capacity;
Map<Integer,Integer> map;
public LRUCacheTest(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) {
LRUCacheTest lruCache = new LRUCacheTest(10);
for (int i = 0; i < 10; i++) {
lruCache.map.put(i,i);
System.out.print(lruCache.map.size()+"\t");
}
System.out.println();
System.out.println(lruCache.map);
lruCache.put(10,200);
System.out.println(lruCache.map);
lruCache.put(11,100);
System.out.println(lruCache.map);
lruCache.get(2);
System.out.println(lruCache.map);
}
}
结果来看是正确的,距离当前时间最远的数据被淘汰
使用LinkedHashMap简单方法实现
LinkedHashMap是维护了双向链表的HashMap,保持了插入元素的顺序。
LinkedHashMap提供了一个钩子方法,在新插入元素后可以决定是否删除最老的元素。
复写removeEldestEntry实现
package thread;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUByLinkedHashMap extends LinkedHashMap<Integer,Integer> {
private int maxSize;
public LRUByLinkedHashMap(int maxSize) {
// 容量为最大值/0.75，即最大负载容量为maxSize
// accessOrder=true 根据查询排序，即最近被使用的放到后面
super((int) Math.ceil(maxSize / 0.75) + 1, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
LRUByLinkedHashMap hashMap = new LRUByLinkedHashMap(10);
for (int i = 0; i < 10; i++) {
hashMap.put(i,i);
System.out.print(hashMap.size()+"\t");
}
System.out.println();
System.out.println(hashMap);
hashMap.put(10,200);
System.out.println(hashMap);
hashMap.put(11,100);
System.out.println(hashMap);
hashMap.get(10);
System.out.println(hashMap);
}
}
双链表+hashmap
package thread;
import java.util.HashMap;
import java.util.Map;
public class LRURedis {
private int capacity;
private Map<Integer,ListNode> map;
private ListNode head;
private ListNode tail;
public LRURedis(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;
}
}
}
到此这篇关于浅谈java如何实现Redis的LRU缓存机制的文章就介绍到这了,更多相关java实现Redis的LRU缓存机制内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
