自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

3種堆內(nèi)緩存算法，贈源碼和設(shè)計思路

作者：小姐姐養(yǎng)的狗
存儲 存儲軟件 算法
要說計算機系統(tǒng)里，什么技術(shù)把tradeoff體現(xiàn)的淋漓盡致，那肯定是緩存無疑。為了協(xié)調(diào)高速部件和低速部件的速度差異，加入一個中間緩存層，是解決這種沖突最有效的方案。

 要說計算機系統(tǒng)里，什么技術(shù)把tradeoff體現(xiàn)的淋漓盡致，那肯定是緩存無疑。為了協(xié)調(diào)高速部件和低速部件的速度差異，加入一個中間緩存層，是解決這種沖突最有效的方案。

[[325756]]

其中，JVM堆內(nèi)緩存是緩存體系中重要的一環(huán)，最常用的有FIFO/LRU/LFU三種算法。

  1. FIFO是簡單的隊列，先進先出。
  2. LRU是最近最少使用，優(yōu)先移除最久未使用的數(shù)據(jù)。是時間維度。
  3. LFU是最近最不常用，優(yōu)先移除訪問次數(shù)最少的數(shù)據(jù)。是統(tǒng)計維度。

由于過期也是緩存的一個重要特點。所有在設(shè)計這三種緩存算法時，需要額外的存儲空間去存儲這個過期時間。

以下將討論這三種緩存算法的操作和設(shè)計要點，但暫未考慮高并發(fā)環(huán)境。

FIFO

先進先出，如果緩存容量滿，則優(yōu)先移出最早加入緩存的數(shù)據(jù);其內(nèi)部可以使用隊列實現(xiàn)。

操作

  • Object get(key) ：獲取保存的數(shù)據(jù)，如果數(shù)據(jù)不存在或者已經(jīng)過期，則返回null。
  • void put(key,value,expireTime)：加入緩存。 無論此key是否已存在，均作為新key處理(移除舊key);如果空間不足，則移除已過期的key，如果沒有，則移除最早加入緩存的key。過期時間未指定，則表示永不自動過期。
  • 注意 ，我們允許key是有過期時間的，這一點與普通的FIFO有所區(qū)別，所以在設(shè)計此題時需要注意。(也是面試考察點，偏設(shè)計而非算法)

普通的FIFO或許大家都能很簡單的寫出，增加了過期時間的考慮之后，在設(shè)計時需要多考慮。如下示例，為暫未考慮并發(fā)環(huán)境的FIFO設(shè)計。

設(shè)計思路

1)用普通的hashMap保存緩存數(shù)據(jù)。

2)需要額外的map用來保存key的過期特性，例子中使用了TreeMap，將“剩余存活時間”作為key，利用TreeMap的排序特性。

  1. public class FIFOCache { 
  2.    
  3.     //按照訪問時間排序,保存所有key-value 
  4.     private final Map<String,Value> CACHE = new LinkedHashMap<>(); 
  5.    
  6.     //過期數(shù)據(jù)，只保存有過期時間的key 
  7.     //暫不考慮并發(fā)，我們認為同一個時間內(nèi)沒有重復的key，如果改造的話，可以將value換成set 
  8.     private final TreeMap<Long, String> EXPIRED = new TreeMap<>(); 
  9.    
  10.     private final int capacity; 
  11.    
  12.     public FIFOCache(int capacity) { 
  13.         this.capacity = capacity; 
  14.     } 
  15.    
  16.     public Object get(String key) { 
  17.         // 
  18.         Value value = CACHE.get(key); 
  19.         if (value == null) { 
  20.             return null; 
  21.         } 
  22.    
  23.         //如果不包含過期時間 
  24.         long expired = value.expired; 
  25.         long now = System.nanoTime(); 
  26.         //已過期 
  27.         if (expired > 0 && expired <= now) { 
  28.             CACHE.remove(key); 
  29.             EXPIRED.remove(expired); 
  30.             return null; 
  31.         } 
  32.         return value.value; 
  33.     } 
  34.    
  35.     public void put(String key,Object value) { 
  36.         put(key,value,-1); 
  37.     } 
  38.    
  39.    
  40.     public void put(String key,Object value,int seconds) { 
  41.         //如果容量不足，移除過期數(shù)據(jù) 
  42.         if (capacity < CACHE.size()) { 
  43.             long now = System.nanoTime(); 
  44.             //有過期的,全部移除 
  45.             Iterator<Long> iterator = EXPIRED.keySet().iterator(); 
  46.             while (iterator.hasNext()) { 
  47.                 long _key = iterator.next(); 
  48.                 //如果已過期，或者容量仍然溢出，則刪除 
  49.                 if (_key > now) { 
  50.                     break; 
  51.                 } 
  52.                 //一次移除所有過期key 
  53.                 String _value = EXPIRED.get(_key); 
  54.                 CACHE.remove(_value); 
  55.                 iterator.remove(); 
  56.             } 
  57.         } 
  58.    
  59.         //如果仍然容量不足，則移除最早訪問的數(shù)據(jù) 
  60.         if (capacity < CACHE.size()) { 
  61.             Iterator<String> iterator = CACHE.keySet().iterator(); 
  62.             while (iterator.hasNext() && capacity < CACHE.size()) { 
  63.                 String _key = iterator.next(); 
  64.                 Value _value = CACHE.get(_key); 
  65.                 long expired = _value.expired; 
  66.                 if (expired > 0) { 
  67.                     EXPIRED.remove(expired); 
  68.                 } 
  69.                 iterator.remove(); 
  70.             } 
  71.         } 
  72.    
  73.         //如果此key已存在,移除舊數(shù)據(jù) 
  74.         Value current = CACHE.remove(key); 
  75.         if (current != null && current.expired > 0) { 
  76.             EXPIRED.remove(current.expired); 
  77.         } 
  78.         //如果指定了過期時間 
  79.         if(seconds > 0) { 
  80.             long expireTime = expiredTime(seconds); 
  81.             EXPIRED.put(expireTime,key); 
  82.             CACHE.put(key,new Value(expireTime,value)); 
  83.         } else { 
  84.             CACHE.put(key,new Value(-1,value)); 
  85.         } 
  86.    
  87.     } 
  88.    
  89.     private long expiredTime(int expired) { 
  90.         return System.nanoTime() + TimeUnit.SECONDS.toNanos(expired); 
  91.     } 
  92.    
  93.     public void remove(String key) { 
  94.         Value value = CACHE.remove(key); 
  95.         if(value == null) { 
  96.             return; 
  97.         } 
  98.         long expired = value.expired; 
  99.         if (expired > 0) { 
  100.             EXPIRED.remove(expired); 
  101.         } 
  102.     } 
  103.    
  104.    
  105.     class Value { 
  106.         long expired; //過期時間,納秒 
  107.         Object value; 
  108.         Value(long expired,Object value) { 
  109.             this.expired = expired; 
  110.             this.value = value; 
  111.         } 
  112.     } 
  113. } 

LRU

least recently used，最近最少使用，是目前最常用的緩存算法和設(shè)計方案之一，其移除策略為“當緩存(頁)滿時，優(yōu)先移除最近最久未使用的數(shù)據(jù)”，優(yōu)點是易于設(shè)計和使用，適用場景廣泛。算法可以參考leetcode 146 (LRU Cache)。

操作

  • Object get(key)：從cache中獲取key對應的數(shù)據(jù)，如果此key已過期，移除此key，并則返回null。
  • void put(key,value,expired)：設(shè)置k-v，如果容量不足，則根據(jù)LRU置換算法移除“最久未被使用的key”。 需要注意，根據(jù)LRU優(yōu)先移除已過期的keys，如果沒有，則根據(jù)LRU移除未過期的key。如果未設(shè)定過期時間，則認為永不自動過期。
  • 這里的設(shè)計關(guān)鍵是過期時間特性，這與常規(guī)的LRU有所不同。

設(shè)計思路

  • LRU的基礎(chǔ)算法，需要了解;每次put、get時需要更新key對應的訪問時間，我們需要一個數(shù)據(jù)結(jié)構(gòu)能夠保存key最近的訪問時間且能夠排序。
  • 既然包含過期時間特性，那么帶有過期時間的key需要額外的數(shù)據(jù)結(jié)構(gòu)保存。
  • 暫時不考慮并發(fā)操作;盡量兼顧空間復雜度和時間復雜度。
  • 此題仍然偏向于設(shè)計題，而非純粹的算法題。

此題代碼與FIFO基本相同，唯一不同點為get()方法，對于LRU而言，get方法需要重設(shè)訪問時間(即調(diào)整所在cache中順序)

  1. public Object get(String key) { 
  2.     // 
  3.     Value value = CACHE.get(key); 
  4.     if (value == null) { 
  5.         return null; 
  6.     } 
  7.    
  8.     //如果不包含過期時間 
  9.     long expired = value.expired; 
  10.     long now = System.nanoTime(); 
  11.     //已過期 
  12.     if (expired > 0 && expired <= now) { 
  13.         CACHE.remove(key); 
  14.         EXPIRED.remove(expired); 
  15.         return null; 
  16.     } 
  17.     //相對于FIFO，增加順序重置 
  18.     CACHE.remove(key); 
  19.     CACHE.put(key,value); 
  20.     return value.value; 
  21. } 

LFU

最近最不常用，當緩存容量滿時，移除 訪問次數(shù) 最少的元素，如果訪問次數(shù)相同的元素有多個，則移除最久訪問的那個。設(shè)計要求參見leetcode 460( LFU Cache)

  1. public class LFUCache { 
  2.    
  3.     //主要容器，用于保存k-v 
  4.     private Map<String, Object> keyToValue = new HashMap<>(); 
  5.    
  6.     //記錄每個k被訪問的次數(shù) 
  7.     private Map<String, Integer> keyToCount = new HashMap<>(); 
  8.    
  9.     //訪問相同次數(shù)的key列表，按照訪問次數(shù)排序，value為相同訪問次數(shù)到key列表。 
  10.     private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>(); 
  11.    
  12.     private int capacity; 
  13.    
  14.     public LFUCache(int capacity) { 
  15.         this.capacity = capacity; 
  16.         //初始化，默認訪問1次，主要是解決下文 
  17.     } 
  18.    
  19.     public Object get(String key) { 
  20.         if (!keyToValue.containsKey(key)) { 
  21.             return null; 
  22.         } 
  23.    
  24.         touch(key); 
  25.         return keyToValue.get(key); 
  26.     } 
  27.    
  28.     /** 
  29.      * 如果一個key被訪問，應該將其訪問次數(shù)調(diào)整。 
  30.      * @param key 
  31.      */   
  32.     private void touch(String key) { 
  33.         int count = keyToCount.get(key); 
  34.         keyToCount.put(key, count + 1);//訪問次數(shù)增加 
  35.         //從原有訪問次數(shù)統(tǒng)計列表中移除 
  36.         countToLRUKeys.get(count).remove(key); 
  37.    
  38.         //如果符合最少調(diào)用次數(shù)到key統(tǒng)計列表為空，則移除此調(diào)用次數(shù)到統(tǒng)計 
  39.         if (countToLRUKeys.get(count).size() == 0) { 
  40.             countToLRUKeys.remove(count); 
  41.         } 
  42.    
  43.         //然后將此key的統(tǒng)計信息加入到管理列表中 
  44.         LinkedHashSet<String> countKeys = countToLRUKeys.get(count + 1); 
  45.         if (countKeys == null) { 
  46.             countKeys = new LinkedHashSet<>(); 
  47.             countToLRUKeys.put(count + 1,countKeys); 
  48.         } 
  49.         countKeys.add(key); 
  50.     } 
  51.    
  52.     public void put(String key, Object value) { 
  53.         if (capacity <= 0) { 
  54.             return; 
  55.         } 
  56.    
  57.         if (keyToValue.containsKey(key)) { 
  58.             keyToValue.put(key, value); 
  59.             touch(key); 
  60.             return; 
  61.         } 
  62.         //容量超額之后，移除訪問次數(shù)最少的元素 
  63.         if (keyToValue.size() >= capacity) { 
  64.             Map.Entry<Integer,LinkedHashSet<String>> entry = countToLRUKeys.firstEntry(); 
  65.             Iterator<String> it = entry.getValue().iterator(); 
  66.             String evictKey = it.next(); 
  67.             it.remove(); 
  68.             if (!it.hasNext()) { 
  69.                 countToLRUKeys.remove(entry.getKey()); 
  70.             } 
  71.             keyToCount.remove(evictKey); 
  72.             keyToValue.remove(evictKey); 
  73.    
  74.         } 
  75.    
  76.         keyToValue.put(key, value); 
  77.         keyToCount.put(key, 1); 
  78.         LinkedHashSet<String> keys = countToLRUKeys.get(1); 
  79.         if (keys == null) { 
  80.             keys = new LinkedHashSet<>(); 
  81.             countToLRUKeys.put(1,keys); 
  82.         } 
  83.         keys.add(key); 
  84.     } 
  85. } 

End本文力求比較三個基本的緩存算法，以便對緩存建設(shè)之路有一個比較籠統(tǒng)的感覺。

更加易用的cache，可以參考guava的實現(xiàn)。謹希望這三個代碼模版，能夠?qū)δ阌兴鶐椭?/p>

作者簡介：小姐姐味道 (xjjdog)，一個不允許程序員走彎路的公眾號。聚焦基礎(chǔ)架構(gòu)和Linux。十年架構(gòu)，日百億流量，與你探討高并發(fā)世界，給你不一樣的味道。

責任編輯：武曉燕 來源： 小姐姐味道
緩存算法贈源碼
相關(guān)推薦

2023-09-17 23:16:46

緩存數(shù)據(jù)庫

2022-08-28 16:31:11

緩存雪崩

2021-07-11 18:06:18

緩存過期淘汰

2016-02-18 10:09:23

12306核心思路架構(gòu)

2021-11-08 11:21:18

redis 淘汰算法

2012-12-17 14:54:55

算法緩存Java

2011-12-06 09:24:10

網(wǎng)頁設(shè)計

2022-04-04 16:53:56

Vue.js設(shè)計框架

2009-06-15 14:15:07

Java設(shè)計模式Java

2018-06-26 15:58:39

進程內(nèi)緩存緩存數(shù)據(jù)

2022-08-17 09:07:09

低代碼LCDP編碼

2024-05-27 00:03:00

Java數(shù)據(jù)JVM

2009-08-14 17:28:14

多表單系統(tǒng)

2021-11-30 10:58:52

算法緩存技術(shù)

2021-10-08 11:45:33

內(nèi)存HeapByteBuf堆內(nèi)

2017-04-10 08:14:28

移動應用應用內(nèi)搜索業(yè)務轉(zhuǎn)化

2022-09-06 15:30:20

緩存一致性

2023-03-27 18:32:30

2023-03-27 21:08:30

2023-12-03 21:52:20

點贊
收藏

51CTO技術(shù)棧公眾號