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
