如何模拟实现一个“缓存”?
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
目录
前言
这次主要实现一个类似缓存的一种数据结构缓存Cache容量有限当容量用完后有新的数据添加进来就需要将原来不常用的数据清除掉再加入新的数据
一、LRU Cache是什么
LRU Cache的底层是一个双向链表 + 哈希表的结构这样做是为了要达到一个时间复杂度为O(1)的存放元素以及获取元素双向链表插入删除元素和哈希表查找元素可以到达O(1)功能是将经常使用的元素放在链表的尾部不常使用的放在链表的头部当容量用完了后再添加元素时就会把头部不经常用的元素删除掉
二、模拟实现
2.1、通过继承 LinkedHashMap 模拟实现
LinkedHashMap 底层也是双向链表 + 哈希表其中有一个构造方法若参数置为 false 时会按照插入顺序进行排序若参数置为 true 时会按照访问顺序也就是插入和访问都会将当前节点放置到尾部尾部代表的是最近访问的数据我们这里需要模拟实现 LRU Cache 所以参数需要设置为 true
代码如下
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap<Integer, Integer> {
public int capacity;//容量
public LRUCache(int capacity) {
//这里的true代表基于访问顺序
super(capacity, 0.75F, true);
this.capacity = capacity;//指定容量
}
@Override
public Integer get(Object key) {
return super.getOrDefault(key, -1);
}
public Integer put(Integer key, Integer value) {
return super.put(key, value);
}
/**
* 为什么要重写这个方法
* 因为达到某个条件为 true 就会删除头节点
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
2.2、自主模拟实现LRU Cache
2.2.1、LRU Cache的定义
这里只需要顶一个双向链表和一个HashMap即可
import java.util.HashMap;
import java.util.Map;
public class MyLRUCache {
//双向链表
static class DLinkNode {
public int key;
public int value;
public DLinkNode prev;
public DLinkNode next;
public DLinkNode() {
}
public DLinkNode(int key, int value) {
this.key = key;
this.value = value;
}
}
public DLinkNode head;//双向链表的头节点
public DLinkNode tail;//双向链表的尾结点
public int usedSize;//当前双向链表中有效数据的个数
public Map<Integer, DLinkNode> map;
public int capacity;//容量
public MyLRUCache(int capacity) {
this.head = new DLinkNode();
this.tail = new DLinkNode();
head.next = tail;
tail.prev = head;
this.cache = new HashMap<>();
this.capacity = capacity;
}
}
2.2.2、存放结点
首先检查当前结点是否之前存放过若没有存放过就将这个结点存储到尾巴的位置若之前有存储过该节点就把之前的结点移动到尾巴的位置即可
/**
* 存储元素
* @param key
* @param val
*/
public void put(int key, int val) {
//1.查找当前这个keu是不是存储过
DLinkNode node = cache.get(key);
//2.如果没有存储过
if(node == null) {
//2.1需要实例化一个结点
DLinkNode dLinkNode = new DLinkNode(key, val);
//2.2存储到map中
cache.put(key, dLinkNode);
//2.3把该结点存储到链表尾巴
addToTail(dLinkNode);
usedSize++;
//2.4检查当前双向链表的有效数据个数 是不是超过了capacity
if(usedSize > capacity) {
//2.5超过了就要移除头部结点
DLinkNode remNode = removeHead();
//2.6清除cache中的元素
cache.remove(remNode.key);
//2.6usedSize--;
usedSize--;
}
} else {
//3.如果存储过
//3.1更新这个key对应的val
node.val = val;
//3.2然后将该结点移到尾部(因为这个是新插入的数据)
moveToTail(node);
}
}
/**
* 移动当前结点到尾巴结点
* @param node
*/
private void moveToTail(DLinkNode node) {
//1.先删除这个结点
removeNode(node);
//2.添加到尾部
addToTail(node);
}
/**
* 删除指定结点
* @param node
*/
private void removeNode(DLinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* 添加结点到链表的尾部
* @param node
*/
private void addToTail(DLinkNode node) {
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
}
/**
* 删除头部结点
* @return
*/
private DLinkNode removeHead() {
DLinkNode del = head.next;
head.next = del.next;
del.next.prev = head;
return del;
}
2.2.3、访问结点
实际上就是将访问到的结点放到尾巴结点处即可经常使用的
/**
* 访问当前key
* 逻辑将访问的结点放到尾巴
* @param key
* @return
*/
public int get(int key) {
DLinkNode node = cache.get(key);
if(node == null) {
return -1;
}
//把最近经常使用的放到尾巴
moveToTail(node);
return node.val;
}
2.2.4、LRU Cache 完整模拟代码
import java.util.HashMap;
import java.util.Map;
public class MyLRUCache {
//双向链表
static class DLinkNode {
public int key;
public int val;
public DLinkNode prev;
public DLinkNode next;
public DLinkNode() {
}
public DLinkNode(int key, int value) {
this.key = key;
this.val = value;
}
@Override
public String toString() {
return "key=" + key +
", val=" + val;
}
}
public DLinkNode head;//双向链表的头节点
public DLinkNode tail;//双向链表的尾结点
public int usedSize;//当前双向链表中有效数据的个数
public Map<Integer, DLinkNode> cache;
public int capacity;//容量
public MyLRUCache(int capacity) {
this.head = new DLinkNode();
this.tail = new DLinkNode();
head.next = tail;
tail.prev = head;
this.cache = new HashMap<>();
this.capacity = capacity;
}
/**
* 存储元素
* @param key
* @param val
*/
public void put(int key, int val) {
//1.查找当前这个keu是不是存储过
DLinkNode node = cache.get(key);
//2.如果没有存储过
if(node == null) {
//2.1需要实例化一个结点
DLinkNode dLinkNode = new DLinkNode(key, val);
//2.2存储到map中
cache.put(key, dLinkNode);
//2.3把该结点存储到链表尾巴
addToTail(dLinkNode);
usedSize++;
//2.4检查当前双向链表的有效数据个数 是不是超过了capacity
if(usedSize > capacity) {
//2.5超过了就要移除头部结点
DLinkNode remNode = removeHead();
//2.6清除cache中的元素
cache.remove(remNode.key);
//2.6usedSize--;
usedSize--;
}
} else {
//3.如果存储过
//3.1更新这个key对应的val
node.val = val;
//3.2然后将该结点移到尾部(因为这个是新插入的数据)
moveToTail(node);
}
}
/**
* 移动当前结点到尾巴结点
* @param node
*/
private void moveToTail(DLinkNode node) {
//1.先删除这个结点
removeNode(node);
//2.添加到尾部
addToTail(node);
}
/**
* 删除指定结点
* @param node
*/
private void removeNode(DLinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* 添加结点到链表的尾部
* @param node
*/
private void addToTail(DLinkNode node) {
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
}
/**
* 删除头部结点
* @return
*/
private DLinkNode removeHead() {
DLinkNode del = head.next;
head.next = del.next;
del.next.prev = head;
return del;
}
/**
* 访问当前key
* 逻辑将访问的结点放到尾巴
* @param key
* @return
*/
public int get(int key) {
DLinkNode node = cache.get(key);
if(node == null) {
return -1;
}
//把最近经常使用的放到尾巴
moveToTail(node);
return node.val;
}
public void printNode(String str) {
DLinkNode cur = head.next;
while( cur != tail) {
System.out.println(cur);
cur = cur.next;
}
}
}
小结
建议多写多练~