浅谈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 == null) {
      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);
    cache.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，线程安全等。

到此这篇关于浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存的文章就介绍到这了,更多相关Java基于LRU时间复杂度为O(1)的缓存内容请搜索考高分网以前的文章或继续浏览下面的相关文章希望大家以后多多支持考高分网！