昨天面試被問到的 快取淘汰演算法FIFO、LRU、LFU及Java實作

快取淘汰演算法

在高并發、高性能的質量要求不斷提高時，我們首先會想到的就是利用快取予以應對，

第一次請求時把計算好的結果存放在快取中，下次遇到同樣的請求時，把之前保存在快取中的資料直接拿來使用，

但是，快取的空間一般都是有限，不可能把所有的結果全部保存下來，那么，當快取空間全部被占滿再有新的資料需要被保存，就要決定洗掉原來的哪些資料，如何做這樣決定需要使用快取淘汰演算法，

常用的快取淘汰演算法有：FIFO、LRU、LFU，下面我們就逐一介紹一下，

FIFO

FIFO，First In First Out，先進先出演算法，判斷被存盤的時間，離目前最遠的資料優先被淘汰，簡單地說，先存入快取的資料，先被淘汰，

最早存入快取的資料，其不再被使用的可能性比剛存入快取的可能性大，建立一個FIFO佇列，記錄所有在快取中的資料，當一條資料被存入快取時，就把它插在隊尾上，需要被淘汰的資料一直在佇列頭，這種演算法只是在按線性順序訪問資料時才是理想的，否則效率不高，因為那些常被訪問的資料，往往在快取中也停留得最久，結果它們卻因變“老”而不得不被淘汰出去，

FIFO演算法用佇列實作就可以了，這里就不做代碼實作了，

LRU

LRU，Least Recently Used，最近最少使用演算法，判斷最近被使用的時間，目前最遠的資料優先被淘汰，簡單地說，LRU 的淘汰規則是基于訪問時間，

如果一個資料在最近一段時間沒有被使用到，那么可以認為在將來它被使用的可能性也很小，因此，當快取空間滿時，最久沒有使用的資料最先被淘汰，

在Java中，其實LinkedHashMap已經實作了LRU快取淘汰演算法，需要在建構式第三個引數傳入true，表示按照時間順序訪問，可以直接繼承LinkedHashMap來實作，

package one.more;

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    /**
     * 容量限制
     */
    private int capacity;

    LruCache(int capacity) {
        // 初始大小，0.75是裝載因子，true是表示按照訪問時間排序
        super(capacity, 0.75f, true);
        //快取最大容量
        this.capacity = capacity;
    }

    /**
     * 重寫removeEldestEntry方法，如果快取滿了，則把鏈表頭部第一個節點和對應的資料洗掉，
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

我寫一個簡單的程式測驗一下：

package one.more;

public class TestApp {

    public static void main(String[] args) {
        LruCache<String, String> cache = new LruCache(3);
        cache.put("keyA", "valueA");
        System.out.println("put keyA");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyB", "valueB");
        System.out.println("put keyB");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyC", "valueC");
        System.out.println("put keyC");
        System.out.println(cache);
        System.out.println("=========================");

        cache.get("keyA");
        System.out.println("get keyA");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyD", "valueD");
        System.out.println("put keyD");
        System.out.println(cache);
    }
}

運行結果如下：

put keyA
{keyA=valueA}
=========================
put keyB
{keyA=valueA, keyB=valueB}
=========================
put keyC
{keyA=valueA, keyB=valueB, keyC=valueC}
=========================
get keyA
{keyB=valueB, keyC=valueC, keyA=valueA}
=========================
put keyD
{keyC=valueC, keyA=valueA, keyD=valueD}

當然，這個不是面試官想要的，也不是我們想要的，我們可以使用雙向鏈表和哈希表進行實作，哈希表用于存盤對應的資料，雙向鏈表用于資料被使用的時間先后順序，

在訪問資料時，如果資料已存在快取中，則把該資料的對應節點移到鏈表尾部，如此操作，在鏈表頭部的節點則是最近最少使用的資料，

當需要添加新的資料到快取時，如果該資料已存在快取中，則把該資料對應的節點移到鏈表尾部；如果不存在，則新建一個對應的節點，放到鏈表尾部；如果快取滿了，則把鏈表頭部第一個節點和對應的資料洗掉，

package one.more;

import java.util.HashMap;
import java.util.Map;

public class LruCache<K, V> {

    /**
     * 頭結點
     */
    private Node head;
    /**
     * 尾結點
     */
    private Node tail;
    /**
     * 容量限制
     */
    private int capacity;
    /**
     * key和資料的映射
     */
    private Map<K, Node> map;

    LruCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }

    public V put(K key, V value) {
        Node node = map.get(key);
        // 資料存在，將節點移動到隊尾
        if (node != null) {
            V oldValue = node.value;
            //更新資料
            node.value = value;
            moveToTail(node);
            return oldValue;
        } else {
            Node newNode = new Node(key, value);
            // 資料不存在，判斷鏈表是否滿
            if (map.size() == capacity) {
                // 如果滿，則洗掉隊首節點，更新哈希表
                map.remove(removeHead().key);
            }
            // 放入隊尾節點
            addToTail(newNode);
            map.put(key, newNode);
            return null;
        }
    }

    public V get(K key) {
        Node node = map.get(key);
        if (node != null) {
            moveToTail(node);
            return node.value;
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LruCache{");
        Node curr = this.head;
        while (curr != null) {
            if(curr != this.head){
                sb.append(',').append(' ');
            }
            sb.append(curr.key);
            sb.append('=');
            sb.append(curr.value);
            curr = curr.next;
        }
        return sb.append('}').toString();
    }

    private void addToTail(Node newNode) {
        if (newNode == null) {
            return;
        }
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            //連接新節點
            tail.next = newNode;
            newNode.pre = tail;
            //更新尾節點指標為新節點
            tail = newNode;
        }
    }

    private void moveToTail(Node node) {
        if (tail == node) {
            return;
        }
        if (head == node) {
            head = node.next;
            head.pre = null;
        } else {
            //調整雙向鏈表指標
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.pre = tail;
        node.next = null;
        tail.next = node;
        tail = node;
    }

    private Node removeHead() {
        if (head == null) {
            return null;
        }
        Node res = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = res.next;
            head.pre = null;
            res.next = null;
        }
        return res;
    }

    class Node {
        K key;
        V value;
        Node pre;
        Node next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

再次運行測驗程式，結果如下：

put keyA
LruCache{keyA=valueA}
=========================
put keyB
LruCache{keyA=valueA, keyB=valueB}
=========================
put keyC
LruCache{keyA=valueA, keyB=valueB, keyC=valueC}
=========================
get keyA
LruCache{keyB=valueB, keyC=valueC, keyA=valueA}
=========================
put keyD
LruCache{keyC=valueC, keyA=valueA, keyD=valueD}

LFU

LFU，Least Frequently Used，最不經常使用演算法，在一段時間內，資料被使用次數最少的，優先被淘汰，簡單地說，LFU 的淘汰規則是基于訪問次數，

如果一個資料在最近一段時間很少被使用到，那么可以認為在將來它被使用的可能性也很小，因此，當空間滿時，最小頻率使用的資料最先被淘汰，

我們可以使用雙哈希表進行實作，一個哈希表用于存盤對應的資料，另一個哈希表用于存盤資料被使用次數和對應的資料，

package one.more;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class LfuCache<K, V> {

    /**
     * 容量限制
     */
    private int capacity;

    /**
     * 當前最小使用次數
     */
    private int minUsedCount;

    /**
     * key和資料的映射
     */
    private Map<K, Node> map;
    /**
     * 資料頻率和對應資料組成的鏈表
     */
    private Map<Integer, List<Node>> usedCountMap;

    public LfuCache(int capacity) {
        this.capacity = capacity;
        this.minUsedCount = 1;
        this.map = new HashMap<>();
        this.usedCountMap = new HashMap<>();
    }

    public V get(K key) {

        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        // 增加資料的訪問頻率
        addUsedCount(node);
        return node.value;
    }

    public V put(K key, V value) {
        Node node = map.get(key);
        if (node != null) {
            // 如果存在則增加該資料的訪問頻次
            V oldValue = node.value;
            node.value = value;
            addUsedCount(node);
            return oldValue;
        } else {
            // 資料不存在，判斷鏈表是否滿
            if (map.size() == capacity) {
                // 如果滿，則洗掉隊首節點，更新哈希表
                List<Node> list = usedCountMap.get(minUsedCount);
                Node delNode = list.get(0);
                list.remove(delNode);
                map.remove(delNode.key);
            }
            // 新增資料并放到資料頻率為1的資料鏈表中
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            List<Node> list = usedCountMap.get(1);
            if (list == null) {
                list = new LinkedList<>();
                usedCountMap.put(1, list);
            }

            list.add(newNode);
            minUsedCount = 1;
            return null;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LfuCache{");
        List<Integer> usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());
        usedCountList.sort(Comparator.comparingInt(i -> i));
        int count = 0;
        for (int usedCount : usedCountList) {
            List<Node> list = this.usedCountMap.get(usedCount);
            if (list == null) {
                continue;
            }
            for (Node node : list) {
                if (count > 0) {
                    sb.append(',').append(' ');
                }
                sb.append(node.key);
                sb.append('=');
                sb.append(node.value);
                sb.append("(UsedCount:");
                sb.append(node.usedCount);
                sb.append(')');
                count++;
            }
        }
        return sb.append('}').toString();
    }

    private void addUsedCount(Node node) {
        List<Node> oldList = usedCountMap.get(node.usedCount);
        oldList.remove(node);

        // 更新最小資料頻率
        if (minUsedCount == node.usedCount && oldList.isEmpty()) {
            minUsedCount++;
        }

        node.usedCount++;
        List<Node> set = usedCountMap.get(node.usedCount);
        if (set == null) {
            set = new LinkedList<>();
            usedCountMap.put(node.usedCount, set);
        }
        set.add(node);
    }

    class Node {

        K key;
        V value;
        int usedCount = 1;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

再次運行測驗程式，結果如下：

put keyA
LfuCache{keyA=valueA(UsedCount:1)}
=========================
put keyB
LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}
=========================
put keyC
LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}
=========================
get keyA
LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}
=========================
put keyD
LfuCache{keyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)}

總結

看到這里，你已經超越了大多數人！

• FIFO，First In First Out，先進先出演算法，判斷被存盤的時間，離目前最遠的資料優先被淘汰，可以使用佇列實作，
• LRU，Least Recently Used，最近最少使用演算法，判斷最近被使用的時間，目前最遠的資料優先被淘汰，可以使用雙向鏈表和哈希表實作，
• LFU，Least Frequently Used，最不經常使用演算法，在一段時間內，資料被使用次數最少的，優先被淘汰，可以使用雙哈希表實作，