Java實(shí)現(xiàn)LRU緩存的實(shí)例詳解

1.Cache

Cache對(duì)于代碼系統(tǒng)的加速與優(yōu)化具有極大的作用，對(duì)于碼農(nóng)來說是一個(gè)很熟悉的概念?？梢哉f，你在內(nèi)存中new 了一個(gè)一段空間（比方說數(shù)組，list）存放一些冗余的結(jié)果數(shù)據(jù)，并利用這些數(shù)據(jù)完成了以空間換時(shí)間的優(yōu)化目的，你就已經(jīng)使用了cache。

有服務(wù)級(jí)的緩存框架，如memcache，Redis等。其實(shí)，很多時(shí)候，我們?cè)谧约和粋€(gè)服務(wù)內(nèi)，或者單個(gè)進(jìn)程內(nèi)也需要緩存，例如，lucene就對(duì)搜索做了緩存，而無須依賴外界。那么，我們?nèi)绾螌?shí)現(xiàn)我們自己的緩存？還要帶自動(dòng)失效的，最好還是LRU（Least Recently Used）。

當(dāng)你思考怎么去實(shí)現(xiàn)，你可能會(huì)想得很遠(yuǎn)。為了LRU，需要把剛使用的數(shù)據(jù)存入棧，或者紀(jì)錄每個(gè)數(shù)據(jù)最近使用的時(shí)間，再來的定時(shí)掃描失效的線程….其實(shí)，Java本身就已經(jīng)為我們提供了LRU Cache很好的實(shí)現(xiàn)，即LinkedHashMap。

2.LinkedHashMap分析

很多沒有去細(xì)究過其內(nèi)部實(shí)現(xiàn)的人，只是將其當(dāng)作一個(gè)普通的hashMap來對(duì)待。LinkedHashMap是一個(gè)雙向鏈表，加上HashTable的實(shí)現(xiàn)。表現(xiàn)出來與普通HashMap的一個(gè)區(qū)別就是LinkedHashMap會(huì)記錄存入其中的數(shù)據(jù)的順序，并能按順取出。
為了實(shí)現(xiàn)，一個(gè)hash表，自然應(yīng)該先申請(qǐng)?jiān)谝黄B續(xù)的內(nèi)存空間上。當(dāng)需要存入數(shù)據(jù)的時(shí)候，根據(jù)相應(yīng)的hash值存入。而LinkedHashMap在這個(gè)基礎(chǔ)上，為每個(gè)entry設(shè)置了before與after屬性，形了一個(gè)雙向鏈表，記錄了他們put進(jìn)入的前后順序。

不僅如此，每當(dāng)通過get來獲得某個(gè)元素后，get方法內(nèi)部，會(huì)在最后通過afterNodeAccess方法來調(diào)整鏈表的指向:

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中，只要滿足條件，便移除最老的數(shù)據(jù),即鏈表的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);
  }
} 

可見，當(dāng)你為L(zhǎng)inkedHashMap設(shè)置有限空間的時(shí)候，自然便完成了LRU Cache的效果。當(dāng)然還有一個(gè)前提，你必須重寫一個(gè)方法removeEldestEntry,返回true。表示空間已滿時(shí)，刪除最老的。

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

3.線程安全的LRU Cache

如此，我們就獲得了一個(gè)LRU緩存利器，滿足了我們大多場(chǎng)景下的需求。但還有一個(gè)問題，它不是線程安全的。在多線程的情況下，你有可能需要對(duì)某些Cache做同步處理。這時(shí)候，你再找，可以看到j(luò)ava有ConcurrentHashMap的實(shí)現(xiàn)，但并不存在ConcurrentLinkedHashMap這樣的類。

當(dāng)然這個(gè)問題也不大，我們可以對(duì)再有的LinkedHashMap，再作封裝，對(duì)get，put, 之類的方法加上同步操作。

目前，我們所用的處理，是直接采和google提供的guava包，這里面就提供了我們想要的ConcurrentLinkedHashMap。這樣就可以很方便地實(shí)現(xiàn)一個(gè)線程安全。具體代碼如下:

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();
 }
}

以上就是Java實(shí)現(xiàn)LRU緩存的實(shí)例，如有疑問請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

最新評(píng)論