溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

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

發(fā)布時間：2020-08-26 16:09:42 來源：腳本之家 閱讀：140 作者：lqh 欄目：編程語言

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

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。

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

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

2.LinkedHashMap分析

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

不僅如此，每當(dāng)通過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);
  }
}

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

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

3.線程安全的LRU Cache

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

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

目前，我們所用的處理，是直接采和google提供的guava包，這里面就提供了我們想要的ConcurrentLinkedHashMap。這樣就可以很方便地實(shí)現(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實(shí)現(xiàn)LRU緩存的實(shí)例，如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手