java - 为什么双端队列(ArrayDeque)容量是2的幂？

Question

在 Java 中(但在 PHP 中类似)ArrayDeque 实现始终具有 2 的幂:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ArrayDeque.java#l126

对于HashMap，这个选择很明确——基于修剪后的 32 位散列具有统一的元素分布。但是 Deque 按顺序插入/删除元素。

此外，ArrayList 不将其容量限制为 2 的幂，只是确保它至少是元素的数量。

那么，为什么 Deque 实现要求它的容量是 2 的幂？

Answer 1

我想，出于性能原因。例如，让我们看一下 addLast 函数的实现:

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

因此，可以编写 tail = (tail + 1) & (elements.length - 1) 而不是 tail = (tail + 1) % elements.length code>(& 比 % 工作得更快)。此类构造在 ArrayDeque 的源代码中多次使用。