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

更新時間：2017年08月14日 11:42:14 投稿：lqh

這篇文章主要介紹了Java實現(xiàn)LRU緩存的實例詳解的相關(guān)資料,這里提供實例幫助大家理解掌握這部分內(nèi)容，需要的朋友可以參考下

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

1.Cache

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

有服務級的緩存框架，如memcache，Redis等。其實，很多時候，我們在自己同一個服務內(nèi)，或者單個進程內(nèi)也需要緩存，例如，lucene就對搜索做了緩存，而無須依賴外界。那么，我們?nèi)绾螌崿F(xiàn)我們自己的緩存？還要帶自動失效的，最好還是LRU（Least Recently Used）。

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

2.LinkedHashMap分析

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

不僅如此，每當通過get來獲得某個元素后，get方法內(nèi)部，會在最后通過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);
  }
}

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

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

3.線程安全的LRU Cache

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

當然這個問題也不大，我們可以對再有的LinkedHashMap，再作封裝，對get，put, 之類的方法加上同步操作。

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

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實現(xiàn)LRU緩存的實例，如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: