java - 为什么 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 的幂呢？

标签： javadequecapacityarraydeque

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这种结构在的源代码中多次使用。