歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Java實現LRU緩存

1.Cache

Cache對於代碼系統的加速與優化具有極大的作用,對於碼農來說是一個很熟悉的概念。可以說,你在內存中new 了一個一段空間(比方說數組,list)存放一些冗余的結果數據,並利用這些數據完成了以空間換時間的優化目的,你就已經使用了cache。
有服務級的緩存框架,如memcache,Redis等。其實,很多時候,我們在自己同一個服務內,或者單個進程內也需要緩存,例如,lucene就對搜索做了緩存,而無須依賴外界。那麼,我們如何實現我們自己的緩存?還要帶自動失效的,最好還是LRU(Least Recently Used)。

當你思考怎麼去實現,你可能會想得很遠。為了LRU,需要把剛使用的數據存入棧,或者紀錄每個數據最近使用的時間,再來的定時掃描失效的線程….其實,Java本身就已經為我們提供了LRU Cache很好的實現,即LinkedHashMap。

2.LinkedHashMap分析

很多沒有去細究過其內部實現的人,只是將其當作一個普通的hashMap來對待。LinkedHashMap是一個雙向鏈表,加上HashTable的實現。表現出來與普通HashMap的一個區別就是LinkedHashMap會記錄存入其中的數據的順序,並能按順取出。
為了實現,一個hash表,自然應該先申請在一片連續的內存空間上。當需要存入數據的時候,根據相應的hash值存入。而LinkedHashMap在這個基礎上,為每個entry設置了before與after屬性,形了一個雙向鏈表,記錄了他們put進入的前後順序。

不僅如此,每當通過get來獲得某個元素後,get方法內部,會在最後通過afterNodeAccess方法來調整鏈表的指向:

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

上述代碼將Node e移至了雙向鏈表的未尾。而在方法afterNodeInsertion中,只要滿足條件,便移除最老的數據,即鏈表的head。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
} 

可見,當你為LinkedHashMap設置有限空間的時候,自然便完成了LRU Cache的效果。當然還有一個前提,你必須重寫一個方法removeEldestEntry,返回true。表示空間已滿時,刪除最老的。

@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){     
    return size()>capacity;        
}

3.線程安全的LRU Cache

如此,我們就獲得了一個LRU緩存利器,滿足了我們大多場景下的需求。但還有一個問題,它不是線程安全的。在多線程的情況下,你有可能需要對某些Cache做同步處理。這時候,你再找,可以看到java有ConcurrentHashMap的實現,但並不存在ConcurrentLinkedHashMap這樣的類。
當然這個問題也不大,我們可以對再有的LinkedHashMap,再作封裝,對get,put, 之類的方法加上同步操作。

目前,我們所用的處理,是直接采和google提供的guava包,這裡面就提供了我們想要的ConcurrentLinkedHashMap。這樣就可以很方便地實現一個線程安全。具體代碼如下:

import java.util.Set;

  import com.googlecode.concurrentlinkedhashmap.Weighers;
  import com.googlecode.concurrentlinkedhashmap.ConcurrentLinkedHashMap;
  public class ConcurrentLRUCache<K, V> {
     public static final int                     DEFAULT_CONCURENCY_LEVEL = 32;

  private final ConcurrentLinkedHashMap<K, V> map;


  public ConcurrentLRUCache(int capacity) {
      this(capacity, DEFAULT_CONCURENCY_LEVEL);
  }

  public ConcurrentLRUCache(int capacity, int concurrency) {
      map = new ConcurrentLinkedHashMap.Builder<K, V>().weigher(Weighers.<V> singleton())
        .initialCapacity(capacity).maximumWeightedCapacity(capacity)
        .concurrencyLevel(concurrency).build();
  }

  public void put(K key, V value) {
      map.put(key, value);
  }

  public V get(K key) {
      V v = map.get(key);
      return v;
  }

  public V getInternal(K key) {
      return map.get(key);
  }

  public void remove(K key) {
      map.remove(key);
  }

  public long getCapacity() {
      return map.capacity();
  }


  public void updateCapacity(int capacity) {
      map.setCapacity(capacity);
  }


  public int getSize() {
      return map.size();
  }


  public void clear() {
      map.clear();
  }

  public Set<K> getKeySet() {
      return map.keySet();
  }
}

Copyright © Linux教程網 All Rights Reserved