Java实现一个LRU缓存,面试我用TreeMap模拟ZSet做的实现
开放中
Java实现一个LRU缓存,面试我用TreeMap模拟ZSet做的实现
在Java中,实现一个LRU(Least Recently Used)缓存通常可以通过 LinkedHashMap 来完成,因为它内部维护了元素的插入顺序。但是,如果你想使用 TreeMap 来模拟一个类似 Redis 的 ZSet 结构来实现 LRU 缓存,你可以使用 TreeMap 来根据时间戳排序元素,以此来模拟最近最少使用的缓存淘汰策略。
以下是使用 TreeMap 实现的一个简单的 LRU 缓存的示例代码:
import java.util.Map;
import java.util.TreeMap;
public class LRUCacheWithTreeMap<K, V> {
private final int capacity;
private long currentTime = 0L;
private final Map<K, V> cache;
private final TreeMap<Long, K> sortedByAccessTime;
public LRUCacheWithTreeMap(int capacity) {
this.capacity = capacity;
this.cache = new TreeMap<>();
this.sortedByAccessTime = new TreeMap<>();
}
public V get(K key) {
if (!cache.containsKey(key)) {
return null;
}
// 更新访问时间
updateAccessTime(key);
return cache.get(key);
}
public void put(K key, V value) {
if (cache.containsKey(key)) {
// 更新访问时间
updateAccessTime(key);
} else {
if (cache.size() >= capacity) {
// 缓存已满,移除最久未使用的元素
evict();
}
// 添加新元素
cache.put(key, value);
sortedByAccessTime.put(currentTime, key);
}
}
private void updateAccessTime(K key) {
// 查找并移除旧的访问时间
for (Map.Entry<Long, K> entry : sortedByAccessTime.entrySet()) {
if (entry.getValue().equals(key)) {
sortedByAccessTime.remove(entry.getKey());
break;
}
}
// 插入新的访问时间
sortedByAccessTime.put(currentTime++, key);
}
private void evict() {
if (sortedByAccessTime.isEmpty()) {
return;
}
// 移除最久未使用的元素
Map.Entry<Long, K> oldestEntry = sortedByAccessTime.pollFirstEntry();
if (oldestEntry != null) {
cache.remove(oldestEntry.getValue());
}
}
}
在这个实现中,我们使用了两个 TreeMap,一个用于存储缓存的键值对,另一个用于按访问时间排序的键。每次访问或添加元素时,我们都会更新访问时间。当缓存达到其容量时,我们会移除最久未使用的元素。
请注意,这个实现并不是线程安全的。如果你需要在多线程环境中使用它,你需要添加适当的同步控制,例如使用 synchronized
关键字或者 ReentrantReadWriteLock
。
此外,这个实现的效率并不是特别高,因为每次更新访问时间时都需要遍历 sortedByAccessTime
来查找旧的访问时间。在实际面试中,面试官可能会要求你提供一个更高效的实现,或者解释为什么选择使用 TreeMap 而不是 LinkedHashMap。
请注册或登录再回复