Guava 有限大小队列 (EvictingQueue) 介绍和分析

在实际场景中总会遇到这样的需求:

需要一个先进先出(FiFo)的队列,其大小是一定的,往队列中插值时,如果队列已经填满了,则移出队列的第一个元素。即所谓的有限大小的队列。

当然,我们能想到的 Guava 也想到了,它提供了的 EvictingQueue 类可以满足上述需求。

简单使用

先来个简单示例,创建一个大小为 3 的 EvictingQueue,循环往队列中添加 6 个元素,再打印出队列中元素情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@Test
public void test() {
EvictingQueue<Integer> queue = EvictingQueue.create(3);
for (int i = 0; i < 6; i++) {
queue.add(i);
System.out.println("添加元素:" + i);
System.out.println("当前队列中元素集合:" + StringUtils.join(queue.iterator(), ',') + "\n");
}
}

// 输出:
添加元素:0
当前队列中元素集合:0

添加元素:1
当前队列中元素集合:0,1

添加元素:2
当前队列中元素集合:0,1,2

添加元素:3
当前队列中元素集合:1,2,3

添加元素:4
当前队列中元素集合:2,3,4

添加元素:5
当前队列中元素集合:3,4,5

可以看出,当添加元素 4 时,队列的元素变成了 2,3,4,原先队列头部的 1 去掉了;再添加元素 5 时,队列头部的 2 又去掉了。

与上面描述的需求一致。

源码分析

EvictingQueue 内部维护了两个重要的成员属性:maxSize 和 delegate。

maxSize 表示队列的最大长度,而且是 final 的,代表初始化后不能改变;delegate 是真正维护元素的队列,EvictingQueue 使用的是 JDK 的 ArrayDeque,它是一个数组结构的双端队列。

1
2
3
4
5
6
7
8
9
private final Queue<E> delegate;

final int maxSize;

private EvictingQueue(int maxSize) {
checkArgument(maxSize >= 0, "maxSize (%s) must >= 0", maxSize);
this.delegate = new ArrayDeque<E>(maxSize);
this.maxSize = maxSize;
}

EvictingQueue 与普通队列的不同在于 add 方法:

1
2
3
4
5
6
7
8
9
10
11
public boolean add(E e) {
checkNotNull(e); // check before removing
if (maxSize == 0) {
return true;
}
if (size() == maxSize) {
delegate.remove();
}
delegate.add(e);
return true;
}

在执行添加元素前,会判断当队列大小达到 maxSize 时,调用 ArrayDeque 的 remove 方法,这个方法会移除队列头部元素。

其它的常用方法都是直接调用 ArrayDeque 的对应方法:

1
2
3
4
5
6
7
8
9
@Override
public boolean contains(Object object) {
return delegate().contains(checkNotNull(object));
}

@Override
public boolean remove(Object object) {
return delegate().remove(checkNotNull(object));
}

总的来说 EvictingQueue 类似一个 ArrayDeque 的包装类,重写了 ArrayDeque 的 add 方法,其它特性与 ArrayDeque 没什么区别。

补充

除了 Guava 的 EvictingQueue 外,Apache commons-collections 包也提供了类似的类:CircularFifoQueue。

它的原理则是直接操作内部维护的一个固定长度数组,通过控制游标的方式删除、添加、遍历元素。