缓存-FIFO算法

FIFO算法简介

    提到FIFO（First In First Out），大家应该都知道这就是队列。队列这种数据结构，主要描述了元素在给定长度的链表中的生命周期。同样的，在缓存中对于有限的存储空间中，我们需要定时的清理缓存中的元素。这个时候FIFO算法就派上用场了。

---

FIFO算法实现

    Java给我们提供了丰富的集合框架，这里我们使用LinkedList来实现，LinkedList实现了Deque接口，而Deque在它的接口说明中我们可以看到这样一句话，This interface extends the Queue interface, When a deque is used as a queue, FIFO behaviro results。通过LinkedList来实现FIFO真的是太简单了。我们只要调用它的两个方法，就可以轻轻松松实现了。下面我们来看一下。

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;
    // 检查头节点是不是存在，如果不存在则抛异常
    if(f == null) 
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 将头节点去掉，将第二个节点作为头节点。
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的缓存实现

    这里我是使用ConcurrentHashMap来存储缓存的键值对，使用LinkedList来存储Key，实现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);
    }

    /**
     * 根据Key取得对应的值
     *
     * @param key
     */
    public void getValue(String key) {
        cache.get(key);
    }

    /**
     * 每次存入Cache中新的元素时，都需要更新我们的队列
     *
     * @param key
     */
    private void cycleKeyQueue(String key) {
        keyQueue.addLast(key);
        // 当前链表的长度与缓存的最大容量做比较
        if (keyQueue.size() > size) {
            // 如果缓存的容量已经超过最大值则移除队头的元素，并移除缓存中的值
            String first = keyQueue.removeFirst();
            cache.remove(first);
        }
    }

    /**
     * 获取Key的列表,方便查看结果
     *
     * @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());
        }
    }
}
// 最后的输出结果
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