手写一个LRU |
您所在的位置：网站首页 › 手写一个lru › 手写一个LRU |
|
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap {
private final int cacheSize;
public LRUCache(int cacheSize) {
// 设置访问顺序为访问顺序，即最近访问的元素将被放置在队列尾部
super((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
this.cacheSize = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
// 当缓存大小超过设定值时，移除最旧（最近最少使用）的元素
return size() > cacheSize;
}
public V get(K key) {
return super.getOrDefault(key, null);
}
public void put(K key, V value) {
super.put(key, value);
}
}
以上代码创建了一个继承自LinkedHashMap的LRUCache类，并重写了removeEldestEntry方法以在缓存满时自动删除最近最少使用的元素。构造函数中的0.75f是LinkedHashMap的负载因子，用于调整map的容量和性能之间的平衡，实际缓存大小我们设为传入参数cacheSize。 注意：这个实现没有处理线程安全问题，如果需要在多线程环境下使用，可以考虑使用ConcurrentHashMap或者其他并发容器，并对put和get操作进行同步控制。 public class LRUCacheExample { public static void main(String[] args) { // 创建一个容量为3的LRU缓存对象 LRUCache cache = new LRUCache(3); // 插入元素 cache.put(1, "One"); cache.put(2, "Two"); cache.put(3, "Three"); // 输出缓存内容（此时应该是1 -> One, 2 -> Two, 3 -> Three） for (Map.Entry entry : cache.entrySet()) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } // 访问已存在的元素，这将更新其在缓存中的位置（最近访问） System.out.println("Get value: " + cache.get(1)); // 插入新的元素，由于缓存已满，最久未使用的键值对将会被移除 cache.put(4, "Four"); // 再次输出缓存内容，此时最旧的键值对1 -> One应该已经被移除 System.out.println("\nAfter adding a new item:"); for (Map.Entry entry : cache.entrySet()) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } } }在上述LRU缓存实现中，当尝试插入第四个键值对（cache.put(4, "Four")）时，由于缓存容量限制为3个元素，且之前已经有三个键值对（1 -> One, 2 -> Two, 3 -> Three）存在，此时缓存已满。 由于LinkedHashMap的特性，在插入新的键值对时，它会自动将新插入的项移动到链表尾部，表示它是最近被访问或修改的。同时，通过重写removeEldestEntry方法，我们设置了当缓存大小超过设定容量（即size() > cacheSize）时，应当移除最旧的条目（即最近最少使用的条目）。 在这个例子中，因为没有其他键值对被访问过，所以最早插入的键值对1 -> One是当前最久未使用的项。因此，当插入第四个键值对时，LinkedHashMap内部机制将会触发removeEldestEntry方法，并返回true，导致键值对1 -> One被自动移除，从而为新的键值对4 -> Four腾出空间。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |