为什么Deque（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写是可能的tail = (tail + 1) & (elements.length - 1)（&比更快%）。这样的构造在ArrayDeque的源代码中已多次使用。