常见缓存置换算法

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哈希