淺談Java如何實(shí)現(xiàn)一個基于LRU時間復(fù)雜度為O(1)的緩存

更新時間：2020年08月03日 16:23:18 作者：碼農(nóng)小麥

這篇文章主要介紹了淺談Java如何實(shí)現(xiàn)一個基于LRU時間復(fù)雜度為O(1)的緩存，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

LRU：Least Recently Used最近最少使用，當(dāng)緩存容量不足時，先淘汰最近最少使用的數(shù)據(jù)。就像JVM垃圾回收一樣，希望將存活的對象移動到內(nèi)存的一端，然后清除其余空間。

緩存基本操作就是讀、寫、淘汰刪除。

讀操作時間復(fù)雜度為O(1)的那就是hash操作了，可以使用HashMap索引 key。

寫操作時間復(fù)雜度為O(1)，使用鏈表結(jié)構(gòu)，在鏈表的一端插入節(jié)點(diǎn)，是可以完成O(1)操作，但是為了配合讀，還要再次將節(jié)點(diǎn)放入HashMap中，put操作最優(yōu)是O(1)，最差是O(n)。

不少童鞋就有疑問了，寫入時又使用map進(jìn)行了put操作，為何緩存不直接使用map？沒錯，首先使用map存儲了節(jié)點(diǎn)數(shù)據(jù)就是采用空間換時間，但是淘汰刪除不好處理，使用map如何去記錄最近最少使用(涉及到時間、頻次問題)。so，使用鏈表可以將活躍節(jié)點(diǎn)移動到鏈表的一端，淘汰時直接從另一端進(jìn)行刪除。

public class LruCache<K,V> {
	/** 這里簡單點(diǎn)直接初始化了*/
  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;
    }
    /** 使用過就移動到右側(cè) */
    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;
      /** 使用過就移動到右側(cè) */
      move2mru(temp);
      return;
    }

		/** 容量滿了清除左側(cè) */
    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機(jī)制。當(dāng)然尚有許多不足，包括緩存移除remove，緩存ttl，線程安全等。

到此這篇關(guān)于淺談Java如何實(shí)現(xiàn)一個基于LRU時間復(fù)雜度為O(1)的緩存的文章就介紹到這了,更多相關(guān)Java基于LRU時間復(fù)雜度為O(1)的緩存內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: