LRU 用 LinkedHashMap 实现
时间: 2024-10-10 20:01:31 浏览: 33
LRU (Least Recently Used) 是一种常用的缓存淘汰策略,它会优先移除最近最少使用的数据项。LinkedHashMap 是 Java 中的一个内置类,非常适合用来实现 LRU 缓存。LinkedHashMap 继承自 HashMap,并添加了链表结构,可以记住元素插入的顺序。
以下是使用 LinkedHashMap 实现 LRU 缓存的基本步骤:
1. 创建 LinkedHashMap 对象,设置其容量大小、初始容量和加载因子(loadFactor),以及是否允许 null 元素(允许的话,null 可以作为最早被淘汰的键值对)。
```java
Map<String, String> lruCache = new LinkedHashMap<>(capacity, loadFactor, true);
```
2. 定义一个固定大小的缓存列表头结点,用于维护访问顺序。当缓存满时,新插入的键值对会替换掉最久未使用的那个。
3. 当向 map 中添加元素时,如果已达到容量,会将最后一个添加的元素从链表头部删除,并将其放入哈希表中,保持链表的头部始终是最新的访问元素。
4. 获取或删除元素时,都会更新该元素在链表中的位置。当调用 `get(key)` 并返回对应的值时,这个 key-value 对会在内部链表中向前移动,表示最近被使用过;如果元素不存在,则返回 null 或者抛出异常。
5. 如果需要清空缓存,可以直接调用 `clear()` 或者遍历 map 删除所有元素。
相关问题
LRU java LinkedHashMap
LRU(Least Recently Used)是一种缓存淘汰策略,即最近最少使用。在Java中,可以使用LinkedHashMap来实现LRU缓存。
LinkedHashMap是HashMap的一个子类,它保留了插入顺序或者是访问顺序。通过设置accessOrder参数为true,可以实现按照访问顺序排序。当缓存满时,可以通过重写removeEldestEntry方法来实现淘汰最近最少使用的元素。
下面是一个简单的LRU缓存实现:
```java
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
```
在这个实现中,我们继承了LinkedHashMap,并重写了removeEldestEntry方法。当缓存大小超过容量时,就会自动删除最近最少使用的元素。
linkedhashmap实现lru
LinkedHashMap可以通过重写removeEldestEntry方法实现LRU(Least Recently Used)算法。具体实现步骤如下:
1. 创建一个LinkedHashMap对象,并设置accessOrder为true,表示按照访问顺序排序。
2. 重写removeEldestEntry方法,当map中的元素个数超过指定的阈值时,删除最近最少使用的元素。
3. 在使用map时,每次访问一个元素时,都会将该元素移到链表的末尾,表示最近使用过。
示例代码如下:
```java
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, .75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
```
在使用LRUCache时,只需要像使用普通的Map一样即可,例如:
```java
LRUCache<Integer, String> cache = new LRUCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);
cache.put(3, "c");
System.out.println(cache); // 输出:{1=a, 3=c}
```
在上述代码中,容量为2,先放入1和2两个元素,然后访问1,再放入3,此时2就会被删除,输出结果为{1=a, 3=c}。
阅读全文