FIFO算法簡介

????提到FIFO（First In First Out），大家應(yīng)該都知道這就是隊列。隊列這種數(shù)據(jù)結(jié)構(gòu)，主要描述了元素在給定長度的鏈表中的生命周期。同樣的，在緩存中對于有限的存儲空間中，我們需要定時的清理緩存中的元素。這個時候FIFO算法就派上用場了。

FIFO算法實(shí)現(xiàn)

????Java給我們提供了豐富的集合框架，這里我們使用LinkedList來實(shí)現(xiàn)，LinkedList實(shí)現(xiàn)了Deque接口，而Deque在它的接口說明中我們可以看到這樣一句話，This interface extends the Queue interface, When a deque is used as a queue, FIFO behaviro results。通過LinkedList來實(shí)現(xiàn)FIFO真的是太簡單了。我們只要調(diào)用它的兩個方法，就可以輕輕松松實(shí)現(xiàn)了。下面我們來看一下。

public void addLast(E e) {
      linkLast(e);
}
// 該方法很簡單，就是將新的元素添加到隊尾
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node(l,e,null);
    last = newNode;
    if(l == null) {
         first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
    modCount++;
}

public E removeFirst(){
    final Node<E> f = first;
    // 檢查頭節(jié)點(diǎn)是不是存在，如果不存在則拋異常
    if(f == null) 
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 將頭節(jié)點(diǎn)去掉，將第二個節(jié)點(diǎn)作為頭節(jié)點(diǎn)。
private E unlinkFirst(Node<E> f) {
     final E element = f.item;
     final Node<E> next = f.next;
     f.item = null;
     f.next = null;
     first = next;
     if(next == null) {
          last = null;
     } else {
          next.prev = null;
     }
     size--;
     modCount++;
     return element;
}

基于FIFO的緩存實(shí)現(xiàn)

????這里我是使用ConcurrentHashMap來存儲緩存的鍵值對，使用LinkedList來存儲Key，實(shí)現(xiàn)FIFO算法，具體代碼如下。

public class FIFOCache {

    private Map<String, String> cache;

    private Integer size;

    private Deque<String> keyQueue;

    public FIFOCache(Integer size) {
        cache = new ConcurrentHashMap<>(size);
        this.size = size;
        keyQueue = new LinkedList<>();
    }

    /**
     * 存緩存
     *
     * @param key
     * @param value
     */
    public void putValue(String key, String value) {
        cycleKeyQueue(key);
        cache.putIfAbsent(key, value);
    }

    /**
     * 刪除元素
     *
     * @param key
     * @param value
     */
    public void delValue(String key, String value) {
        cache.remove(key, value);
        keyQueue.remove(key);
    }

    /**
     * 根據(jù)Key取得對應(yīng)的值
     *
     * @param key
     */
    public void getValue(String key) {
        cache.get(key);
    }

    /**
     * 每次存入Cache中新的元素時，都需要更新我們的隊列
     *
     * @param key
     */
    private void cycleKeyQueue(String key) {
        keyQueue.addLast(key);
        // 當(dāng)前鏈表的長度與緩存的最大容量做比較
        if (keyQueue.size() > size) {
            // 如果緩存的容量已經(jīng)超過最大值則移除隊頭的元素，并移除緩存中的值
            String first = keyQueue.removeFirst();
            cache.remove(first);
        }
    }

    /**
     * 獲取Key的列表,方便查看結(jié)果
     *
     * @return
     */
    public String keyQueue() {
        return String.join(",", keyQueue);
    }
}

????下面是我寫了一個方法來測試我們的FIFOCache

public class App {
    public static void main(String[] args) {
        FIFOCache fifoCache = new FIFOCache(10);
        for (int i = 0; i < 20; ++i) {
            fifoCache.putValue("key_" + i, "value_" + i);
            System.out.println(fifoCache.keyQueue());
        }
    }
}
// 最后的輸出結(jié)果
key_0
key_0,key_1
key_0,key_1,key_2
key_0,key_1,key_2,key_3
key_0,key_1,key_2,key_3,key_4
key_1,key_2,key_3,key_4,key_5
key_2,key_3,key_4,key_5,key_6
key_3,key_4,key_5,key_6,key_7
key_4,key_5,key_6,key_7,key_8
key_5,key_6,key_7,key_8,key_9
key_6,key_7,key_8,key_9,key_10
key_7,key_8,key_9,key_10,key_11
key_8,key_9,key_10,key_11,key_12
key_9,key_10,key_11,key_12,key_13
key_10,key_11,key_12,key_13,key_14
key_11,key_12,key_13,key_14,key_15
key_12,key_13,key_14,key_15,key_16
key_13,key_14,key_15,key_16,key_17
key_14,key_15,key_16,key_17,key_18
key_15,key_16,key_17,key_18,key_19