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

   日期:2020-08-03     浏览:82    评论:0    
核心提示:LRU:Least Recently Used最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据。就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间。缓存基本操作就是读、写、淘汰删除。读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引 key。写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),最差是O(n)。不少童鞋就有疑问了,写

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,线程安全等。

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服