这篇文章主要讲解了Java实现一个基于LRU时间复杂度为O(1)的缓存的方法，内容清晰明了，对此有兴趣的小伙伴可以学习一下，相信大家阅读完之后会有帮助。
LRU：Least Recently Used最近最少使用，当缓存容量不足时，先淘汰最近最少使用的数据。就像JVM垃圾回收一样，希望将存活的对象移动到内存的一端，然后清除其余空间。
缓存基本操作就是读、写、淘汰删除。
读操作时间复杂度为O(1)的那就是hash操作了，可以使用HashMap索引 key。
写操作时间复杂度为O(1)，使用链表结构，在链表的一端插入节点，是可以完成O(1)操作，但是为了配合读，还要再次将节点放入HashMap中，put操作最优是O(1)，最差是O(n)。
不少童鞋就有疑问了，写入时又使用map进行了put操作，为何缓存不直接使用map？没错，首先使用map存储了节点数据就是采用空间换时间，但是淘汰删除不好处理，使用map如何去记录最近最少使用(涉及到时间、频次问题)。so，使用链表可以将活跃节点移动到链表的一端，淘汰时直接从另一端进行删除。
public class LruCache<K,V> {
/** 这里简单点直接初始化了*/
private int capacity = 2;
private int size = 0;
private HashMap<K,DoubleListNode<K,V>> cache = new HashMap<>(capacity);
private DoubleListNode<K,V> lruNode = new DoubleListNode<K, V>(null,null,null,null);
private DoubleListNode<K,V> mruNode = new DoubleListNode<K, V>(null,null,null,null);
public V get(K key){
DoubleListNode<K,V> target = cache.get(key);
if (target == null) {
return null;
}
/** 使用过就移动到右侧 */
move2mru(target);
return target.value;
}
public void put(K key,V value){
if(cache.containsKey(key)){
DoubleListNode<K,V> temp = cache.get(key);
temp.value = value;
/** 使用过就移动到右侧 */
move2mru(temp);
return;
}
/** 容量满了清除左侧 */
if(size >= capacity){
evict4lru();
}
DoubleListNode<K,V> newNode = new DoubleListNode<>(mruNode,null,key,value);
if(size == 0){
lruNode.next = newNode;
}
mruNode.next = newNode;
mruNode = newNode;
cache.put(key,newNode);
size++;
}
private void move2mru(DoubleListNode<K,V> newMru){
DoubleListNode<K,V> pre = newMru.pre;
DoubleListNode<K,V> next = newMru.next;
pre.next = next;
newMru.pre = mruNode;
mruNode.next = newMru;
mruNode = newMru;
}
private void evict4lru(){
cache.remove(lruNode.next.key);
lruNode.next = lruNode.next.next;
size--;
}
public String toString(){
StringBuffer sb = new StringBuffer("lru -> ");
DoubleListNode<K,V> temp = lruNode;
while(temp!=null){
sb.append(temp.key).append(":").append(temp.value);
sb.append(" -> ");
temp = temp.next;
}
sb.append(" -> mru ");
return sb.toString();
}
public static void main(String[] args) {
LruCache<String,String> cache = new LruCache<>();
cache.put("1","1");
System.out.println(cache);
cache.get("1");
cache.put("2","2");
System.out.println(cache);
cache.put("3","3");
System.out.println(cache);
cache.put("4","4");
System.out.println(cache);
}
}
class DoubleListNode<K,V>{
K key;
V value;
DoubleListNode<K,V> pre;
DoubleListNode<K,V> next;
public DoubleListNode(K key,V value){
this.key = key;
this.value = value;
}
public DoubleListNode(DoubleListNode<K,V> pre,DoubleListNode<K,V> next,K key,V value){
this.pre = pre;
this.next = next;
this.key = key;
this.value = value;
}
}这里使用链表，及HashMap完成了基于LRU的缓存，其中HashMap主要用来快速索引key，链表用来完成LRU机制。当然尚有许多不足，包括缓存移除remove，缓存ttl，线程安全等。
看完上述内容，是不是对Java实现一个基于LRU时间复杂度为O(1)的缓存的方法有进一步的了解，如果还想学习更多内容，欢迎关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
