目录
LRUCache
概念
实现原理
基于LinkedHashMap实现LRUCache
主要特点
构造函数
完整代码
代码示例1–基于插入顺序
代码示例2–基于访问顺序
代码示例3–删除最少访问
模拟实现LRUCache
基本框架
存放节点–put()
将节点移至开头–moveToHead()
删除指定节点–removeNode()
将节点放到开头–addToHead()
删除尾部节点–removeTail()
访问指定节点–get()
打印LRUCache
完整代码
代码示例
应用场景
LRUCache优缺点
LRUCache
概念
LRUCache，即最近最少使用缓存（Least Recently Used Cache），是一种常用的缓存替换策略。在缓存系统中，由于缓存空间有限，当缓存满时，需要按照一定的策略替换掉部分旧数据，以便为新数据腾出空间。LRUCache正是基于“最近最少使用”的原则来选择被替换的数据，即认为最近一段时间未被访问的数据在未来被访问的可能性也最小，因此优先替换这些数据。
实现原理
LRUCache的实现通常依赖于哈希表和双向链表两种数据结构的结合。哈希表用于实现数据的快速查找，而双向链表则用于维护数据的使用顺序。具体实现方式如下：
1.哈希表：哈希表的键（Key）为缓存数据的键，值（Value）为双向链表中对应节点的指针或迭代器。这样，在访问缓存数据时，可以通过哈希表快速定位到双向链表中的节点，进而进行访问或更新操作。 2.双向链表：双向链表中的节点按照数据被访问的顺序排列，最近被访问的节点位于链表头部，而最久未被访问的节点则位于链表尾部。当访问或更新某个节点时，将该节点从当前位置删除，并插入到链表头部，以表示该节点是最近被访问的。当缓存满时，则直接删除链表尾部的节点，即最久未被访问的节点，以腾出空间。
使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。
基于LinkedHashMap实现LRUCache
LinkedHashMap 是 Java 集合框架中的一部分，它实现了 Map 接口，并且保持了一个运行于所有条目的双重链接列表。这意味着迭代器会以元素被插入的顺序进行遍历（插入顺序），或者根据访问顺序（访问顺序，即最近最少使用（LRU）缓存策略）来遍历，具体取决于其构造时的配置。
主要特点
1.有序性：LinkedHashMap 维护了一个插入顺序的链表，这使得它能够按照元素被插入的顺序来遍历键值对。如果你需要保持元素插入的顺序，那么 LinkedHashMap 是一个很好的选择。 2.访问顺序：通过构造函数的一个布尔参数，你可以指定 LinkedHashMap 是否应该按照访问顺序来排序键值对，即最近访问的元素会被放在链表的末尾。这种特性使得 LinkedHashMap 非常适合实现缓存，特别是最近最少使用（LRU）缓存。 3.性能：与 HashMap 相比，LinkedHashMap 的性能略低，因为它需要维护一个额外的链表来保持元素的顺序。然而，在需要保持元素顺序的场景下，这种性能损失通常是可接受的。 4.继承结构：LinkedHashMap 继承自 HashMap，因此它继承了 HashMap 的大部分功能，包括快速的查找、插入和删除操作。
构造函数
1.LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：这个构造函数允许你指定初始容量、加载因子和是否按照访问顺序来排序键值对。 2.LinkedHashMap(int initialCapacity, float loadFactor)：这个构造函数与上一个类似，但是它默认不使用访问顺序。 3.LinkedHashMap(int initialCapacity)：这个构造函数仅指定了初始容量，加载因子被设置为默认值（0.75f），并且不使用访问顺序。 4.LinkedHashMap()：使用默认初始容量（16）和加载因子（0.75f) , 并且不使用访问顺序。
完整代码
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);
}
@Override
public Integer put(Integer key, Integer value) {
return super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
代码示例1–基于插入顺序
public static void main(String[] args) {
LinkedHashMap<String,Integer> linkedHashMap =
new LinkedHashMap<>(16,0.7f,false);
linkedHashMap.put("小明",10);
linkedHashMap.put("小花",11);
linkedHashMap.put("小狗",12);
System.out.println(linkedHashMap);
System.out.println("获取元素");
System.out.println(linkedHashMap.get("小花"));
System.out.println(linkedHashMap);
}
运行结果
代码示例2–基于访问顺序
public static void main(String[] args) {
LinkedHashMap<String,Integer> linkedHashMap =
new LinkedHashMap<>(16,0.7f,true);
linkedHashMap.put("小明",10);
linkedHashMap.put("小花",11);
linkedHashMap.put("小狗",12);
System.out.println(linkedHashMap);
System.out.println("获取元素");
System.out.println(linkedHashMap.get("小花"));
System.out.println(linkedHashMap);
}
运行结果：
代码示例3–删除最少访问
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);
lruCache.put(100,10);
lruCache.put(110,11);
lruCache.put(120,12);
System.out.println(lruCache);
System.out.println("获取元素");
System.out.println(lruCache.get(110));
System.out.println(lruCache);
System.out.println(lruCache.get(100));
System.out.println(lruCache);
System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");
lruCache.put(999,99);
System.out.println(lruCache);
}
运行结果：
模拟实现LRUCache
基本框架
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 val) {
this.key = key;
this.val = val;
}
@Override
public String toString() {
return "{ key=" + key +", val=" + val+"} ";
}
}
public DLinkNode head;//双向链表的头节点
public DLinkNode tail;//双向链表的尾节点
public int usedSize;//代表当前双向链表当中 有效的数据个数
public Map<Integer,DLinkNode> cache;//定义一个map
public int capacity;//容量
public MyLRUCache(int capacity) {
this.head = new DLinkNode();
this.tail = new DLinkNode();
head.next = tail;
tail.prev = head;
cache = new HashMap<>();
this.capacity = capacity;
}
}
存放节点–put()
public void put(int key,int val) {
//1. 查找当前的这个key 是不是存储过
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 把该节点存储到链表的开头
addToHead(dLinkNode);
usedSize++;
//2.4 检查当前双向链表的有效数据个数 是不是超过了capacity
if(usedSize > capacity) {
//2.5 超过了，就需要移除尾部的节点
DLinkNode remNode = removeTail();
//2.6 清除cache当中的元素
cache.remove(remNode.key);
//2.7 usedSize–;
usedSize–;
}
printNodes("put");
}else {
//3. 如果存储过
//3.1 更新这个key对应的value
node.val = val;
//3.2 然后将该节点，移动至开头【因为这个是新插入的数据】
moveToHead(node);
}
}
将节点移至开头–moveToHead()
private void moveToHead(DLinkNode node) {
//1. 先删除这个节点
removeNode(node);
//2. 添加到开头
addToHead(node);
}
删除指定节点–removeNode()
private void removeNode(DLinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
将节点放到开头–addToHead()
private void addToHead(DLinkNode node) {
head.next.prev=node;
node.next=head.next;
node.prev=head;
head.next=node;
}
删除尾部节点–removeTail()
private DLinkNode removeTail() {
DLinkNode del = tail.prev;
tail.prev = del.prev;
del.prev.next = tail;
return del;
}
访问指定节点–get()
public int get(int key) {
DLinkNode node = cache.get(key);
if(node == null) {
return -1;
}
//把最近 最多使用的 放到了链表的开头
moveToHead(node);
printNodes("get ");
return node.val;
}
打印LRUCache
public void printNodes(String str) {
System.out.println(str+": ");
DLinkNode cur = head.next;
while (cur != tail) {
System.out.print(cur);
cur = cur.next;
}
System.out.println();
}
完整代码
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 val) {
this.key = key;
this.val = val;
}
@Override
public String toString() {
return "{ key=" + key +", val=" + val+"} ";
}
}
public DLinkNode head;//双向链表的头节点
public DLinkNode tail;//双向链表的尾节点
public int usedSize;//代表当前双向链表当中 有效的数据个数
public Map<Integer,DLinkNode> cache;//定义一个map
public int capacity;//容量
public MyLRUCache(int capacity) {
this.head = new DLinkNode();
this.tail = new DLinkNode();
head.next = tail;
tail.prev = head;
cache = new HashMap<>();
this.capacity = capacity;
}
public void put(int key,int val) {
//1. 查找当前的这个key 是不是存储过
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 把该节点存储到链表的开头
addToHead(dLinkNode);
usedSize++;
//2.4 检查当前双向链表的有效数据个数 是不是超过了capacity
if(usedSize > capacity) {
//2.5 超过了，就需要移除尾部的节点
DLinkNode remNode = removeTail();
//2.6 清除cache当中的元素
cache.remove(remNode.key);
//2.7 usedSize–;
usedSize–;
}
printNodes("put");
}else {
//3. 如果存储过
//3.1 更新这个key对应的value
node.val = val;
//3.2 然后将该节点，移动至开头【因为这个是新插入的数据】
moveToHead(node);
}
}
private void moveToHead(DLinkNode node) {
//1. 先删除这个节点
removeNode(node);
//2. 添加到开头
addToHead(node);
}
private void removeNode(DLinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(DLinkNode node) {
head.next.prev=node;
node.next=head.next;
node.prev=head;
head.next=node;
}
private DLinkNode removeTail() {
DLinkNode del = tail.prev;
tail.prev = del.prev;
del.prev.next = tail;
return del;
}
public int get(int key) {
DLinkNode node = cache.get(key);
if(node == null) {
return -1;
}
//把最近 最多使用的 放到了链表的开头
moveToHead(node);
printNodes("get ");
return node.val;
}
public void printNodes(String str) {
System.out.println(str+": ");
DLinkNode cur = head.next;
while (cur != tail) {
System.out.print(cur);
cur = cur.next;
}
System.out.println();
}
}
代码示例
public static void main(String[] args) {
MyLRUCache lruCache = new MyLRUCache(3);
lruCache.put(100,10);
lruCache.put(110,11);
lruCache.put(120,12);
System.out.println("获取元素");
System.out.println(lruCache.get(110));
System.out.println(lruCache.get(100));
System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");
lruCache.put(999,99);
}
运行结果：
应用场景
LRUCache由于其高效的缓存替换策略，被广泛应用于各种需要缓存的场景中，如：
1.Web缓存：在Web服务器中，LRUCache可以用于缓存用户请求的网页内容，减少对后端2.数据库的访问次数，提高响应速度。 3.数据库缓存：在数据库系统中，LRUCache可以用于缓存查询结果，减少数据库的I/O操作，提高查询效率。 4.操作系统缓存：在操作系统中，LRUCache可以用于缓存文件系统的数据块，减少对硬盘的访问次数，提高文件系统的性能。
LRUCache优缺点
优点：
实现简单，易于理解和维护。 缓存替换效率高，能够较好地反映数据的访问模式。 缺点：
需要额外的空间来存储哈希表和双向链表，增加了内存开销。 在某些情况下，如数据访问模式变化较大时，LRUCache的命中率可能会下降。
