浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

浅谈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 {

/** 这里简单点直接初始化了*/

private int capacity = 2;

private int size = 0;

private HashMap> cache = new HashMap<>(capacity);

private DoubleListNode lruNode = new DoubleListNode(null,null,null,null);

private DoubleListNode mruNode = new DoubleListNode(null,null,null,null);

public V get(K key){

DoubleListNode target = cache.get(key);

if (target == nkdFEuUEqull) {

return null;

}

/** 使用过就移动到右侧 */

move2mru(target);

return target.value;

}

public void put(K key,V value){

if(cache.containsKey(key)){

DoubleListNode temp = cache.get(key);

temp.value = value;

/** 使用过就移动到右侧 */

move2mru(temp);

return;

}

/** 容量满了清除左侧 */

if(size >= capacity){

evict4lru();

}

DoubleListNode 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 newMru){

DoubleListNode pre = newMru.pre;

DoubleListNode 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 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 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);

cachkdFEuUEqe.put("4","4");

System.out.println(cache);

}

}

class DoubleListNode{

K key;

V value;

DoubleListNode pre;

DoubleListNode next;

public DoubleListNode(K key,V value){

this.key = key;

this.value = value;

}

public DoubleListNode(DoubleListNode pre,DoubleListNode next,K key,V value){

this.pre = pre;

this.next = next;

this.key = key;

this.value = value;

}

}

这里使用链表，及HashMap完成了基于LRU的缓存，其中HashMap主要用来快速索引key，链表用来完成LRU机制。当然尚有许多不足，包括缓存移除remove，缓存ttl，线程安全等。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。