常見緩存置換算法

LRU 最近最久未使用
FIFO 先進先出置換算法類似隊列
OPT 最佳置換算法（理想中存在的）
NRU Clock置換算法
LFU 最少使用置換算法
PBA 頁面緩沖算法

LRU

實作原理：連結清單+hash表

查詢插入時間複雜度：O(1)

代碼實作：LinkedHashMap

dubbo的工具LRU工具類便是繼承自LinkedHashMap：com.alibaba.dubbo.common.utils.LRUCache

資料結構

HashMap結構基礎上，為所有Node節點維護一個雙向連結清單，并增加了head，tail指針，如下圖

緩存置換算法之LRU/LFULRULFU實作

代碼實作

put

LinkedHashMap重寫了HashMap的新增節點方法

// 該方法傳回的新增節點存儲之hash表中
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将新增節點維護至雙向連結清單的尾巴節點
    linkNodeLast(p);
    return p;
}
// 将新節點連結至尾巴節點
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

put代碼實作相對來說較為簡單，直接追加至尾巴節點即可，因為新增節點是最新使用的節點

get

LinkedHashMap重寫了HashMap的get方法

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 通過accessOrder屬性決定是否需要維護通路節點至尾巴節點（LRU規則）
    // 該參數不能動态修改，構造方法指定
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
// 移動指定節點至尾巴節點
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 1. 如果目前節點不是尾巴節點則移動
    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)
            // 2. 如果目前節點的父節點為null，将子節點置為head頭節點
            head = a;
        else
            // 3. 如果父節點不為null，将父節點的子節點置為目前節點的子節點
            b.after = a;
        if (a != null)
            // 4. 如果子節點不為null，将子節點的父節點置為目前節點的父節點
            a.before = b;
        else
            // 5. 如果子節點為null，将父節點置為last節點
            last = b;
        if (last == null)
            // 走到此處邏輯的前提條件：b為null(步驟5中的b節點為null），a為null（邏輯走到
            // 步驟5的前提是子節點為null）
            // 
            // 6. 如果父節點為null，子節點也為null，将目前節點置為head頭節點
            head = p;
        else {
            // 7. 如果尾巴節點不為null,目前節點的父節點置為尾巴節點
            p.before = last;
            // 8. 尾巴節點的子節點置為目前節點
            last.after = p;
        }
        // 9. 目前節點置為尾巴節點
        tail = p;
        ++modCount;
    }
}

問題

為什麼LinkedHashMap節點維護的指針為before/after，而不是pre/next？

因為next指針維護的是hash沖突時的連結清單結構的子節點，pre指針維護的是hash沖突時紅黑樹結構的前置節點

LFU實作

實作原理：計數排序+hash表

查詢插入時間複雜度：O(1)

資料結構

緩存置換算法之LRU/LFULRULFU實作

代碼實作

package org.gallant.leetcode.algorithms;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * @author : 會灰翔的灰機
 * @date : 2021/7/31
 */
public class LeastFrequentlyUsedCache {

  private final Map<Integer, CountableData> DATA = new HashMap<>();
  private final Map<Integer, List<CountableData>> COUNTING_SORT = new HashMap<>();

  public void put(Integer key, String value) {
    CountableData countableData = DATA.get(key);
    if (countableData == null) {
      countableData = new CountableData();
      countableData.setCount(0);
      DATA.put(key, countableData);
      initCountingSort(countableData.getCount());
      COUNTING_SORT.get(countableData.getCount()).add(countableData);
    } else {
      int oldCount = countableData.getCount();
      int newCount = oldCount + 1;
      countableData.setCount(newCount);
      initCountingSort(oldCount, newCount);
      COUNTING_SORT.get(oldCount).remove(countableData);
      COUNTING_SORT.get(newCount).add(countableData);
    }
    countableData.setKey(key);
    countableData.setData(value);
  }

  public CountableData get(Integer key) {
    int oldCount = 0;
    int newCount = 1;
    CountableData countableData = DATA.get(key);
    if (countableData == null) {
      return null;
    } else {
      oldCount = countableData.getCount();
      newCount = oldCount + 1;
      countableData.setCount(newCount);
    }
    initCountingSort(oldCount, newCount);
    COUNTING_SORT.get(oldCount).remove(countableData);
    COUNTING_SORT.get(newCount).add(countableData);
    return countableData;
  }

  private void initCountingSort(Integer... counts) {
    Arrays.stream(counts).forEach(count -> COUNTING_SORT.computeIfAbsent(count, k -> new ArrayList<>()));
  }

  public void printData() {
    System.out.println(DATA);
    System.out.println(COUNTING_SORT);
    System.out.println("-----------");
  }

  public void expel() {
    for (Entry<Integer, List<CountableData>> integerListEntry : COUNTING_SORT.entrySet()) {
      Integer k = integerListEntry.getKey();
      List<CountableData> v = integerListEntry.getValue();
      if (v != null && v.size() > 0) {
        v.forEach(countableData -> {
          DATA.remove(countableData.getKey());
          COUNTING_SORT.remove(countableData.getCount());
        });
        break;
      }
    }
  }

  private static class CountableData implements Serializable {

    private static final long serialVersionUID = -1449571685883654388L;
    private Integer key;
    private String data;
    private Integer count;

    public Integer getKey() {
      return key;
    }

    public void setKey(Integer key) {
      this.key = key;
    }

    public Object getData() {
      return data;
    }

    public void setData(String data) {
      this.data = data;
    }

    public Integer getCount() {
      return count;
    }

    public void setCount(Integer count) {
      this.count = count;
    }

    @Override
    public String toString() {
      return "{" + data +
          ", " + count +
          '}';
    }
  }

  public static void main(String[] args) {
    LeastFrequentlyUsedCache cache = new LeastFrequentlyUsedCache();
    for (int i = 0; i < 10; i++) {
      cache.put(i, "data-" + i);
    }
    cache.printData();
    for (int i = 0; i < 3; i++) {
      cache.get(0);
    }
    for (int i = 0; i < 5; i++) {
      cache.get(3);
    }
    cache.printData();
    cache.expel();
    System.out.println("驅逐資料後");
    cache.printData();
  }

}

執行結果

{0={data-0, 0}, 1={data-1, 0}, 2={data-2, 0}, 3={data-3, 0}, 4={data-4, 0}, 5={data-5, 0}, 6={data-6, 0}, 7={data-7, 0}, 8={data-8, 0}, 9={data-9, 0}}
{0=[{data-0, 0}, {data-1, 0}, {data-2, 0}, {data-3, 0}, {data-4, 0}, {data-5, 0}, {data-6, 0}, {data-7, 0}, {data-8, 0}, {data-9, 0}]}
-----------
{0={data-0, 3}, 1={data-1, 0}, 2={data-2, 0}, 3={data-3, 5}, 4={data-4, 0}, 5={data-5, 0}, 6={data-6, 0}, 7={data-7, 0}, 8={data-8, 0}, 9={data-9, 0}}
{0=[{data-1, 0}, {data-2, 0}, {data-4, 0}, {data-5, 0}, {data-6, 0}, {data-7, 0}, {data-8, 0}, {data-9, 0}], 1=[], 2=[], 3=[{data-0, 3}], 4=[], 5=[{data-3, 5}]}
-----------
驅逐資料後
{0={data-0, 3}, 3={data-3, 5}}
{1=[], 2=[], 3=[{data-0, 3}], 4=[], 5=[{data-3, 5}]}
-----------

Process finished with exit code 0

小結

LFU實作方法很多，實作整體思路總結幾點

hash表提供存儲，可以提供高效的通路訴求
為每個value資料存儲通路計數器，每次通路資料都需要額外維護計數器資料
基于計數器對資料進行排序
驅逐排序後通路次數最低的資料

優化方向

排序方法可以按需選擇，選擇适合自己業務訴求的算法，時間優先？還是空間優先？
排序觸發時機，可以按照業務訴求選擇延遲批量排序，而不是實時排序，比如，當計數器發生變更達到某個門檻值時觸發一次排序，或者驅逐前觸發一次排序，按需選擇适合業務需求的就是最好的方案

緩存置換算法之LRU/LFULRULFU實作

LRU

資料結構

代碼實作

put

get

問題

LFU實作

資料結構

代碼實作

執行結果

小結

繼續閱讀

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

supervisor 管理redis 和httpd 環境centos7

Redis簡介一(單機版)發展曆程Redis

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希