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 的幂呢？

score 5 · Accepted Answer

我想，出于性能原因。例如，让我们看一下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这种结构在的源代码中多次使用。

score 4 · Accepted Answer

终于找到了！！！原因不仅在于性能和位掩码操作（是的，它们更快，但并不显着）。真正的原因是如果我们使用顺序添加-删除操作，则允许回送elements容量。换句话说：在remove()操作后重新使用释放的单元格。

考虑以下示例（初始容量为16）：

只有add()：
1. 添加 15 个元素 => 头=0，尾=15
2. 添加更多 5 个元素 => doubleCapacity()=> 头=0，尾=20，容量=32
add()- remove()-add() :
1. 添加 15 个元素 => 头=0，尾=15
2. 删除10 个元素 => 尾循环返回已删除的索引 => 头=10，尾=15
3. 添加更多 5 个元素 => 容量仍为 16，elements[]数组未重建或重新分配！=> 新元素被添加到删除元素的位置到数组的开头 => head=10, tail=4 (从 15->0->1->2->循环回到数组的开头3->4)。注意值 16-19 被插入到索引 0-3

因此，在这种情况下，使用二的幂和简洁的位操作更有意义。使用这种方法，诸如if ( (tail = (tail + 1) & (elements.length - 1)) == head)允许分配和轻松验证循环 tail不与head（是的，实际上尾巴咬头的愚蠢的蛇:)）重叠的操作

要玩的代码片段：

ArrayDeque<String> q = new ArrayDeque<>(15); // capacity is 16

// add 15 elements
q.add("0"); q.add("1"); q.add("2"); q.add("3"); q.add("4");
q.add("5"); q.add("6"); q.add("7"); q.add("8"); q.add("9");
q.add("10"); q.add("11");q.add("12");q.add("13");q.add("14");

// remove 10 elements from the head => tail LOOPS BACK in the elements[]
q.poll();q.poll();q.poll();q.poll();q.poll();q.poll();q.poll();q.poll();q.poll();q.poll();

// add 5 elements => the elements[] is not reallocated!
q.add("15");q.add("16");q.add("17");q.add("18");q.add("19");


q.poll();

score 3 · Accepted Answer

2 的幂适用于某些掩蔽操作。例如，从整数中获取低位位数。

因此，如果大小为 64，则 64-1 为 63，即二进制 111111。

这有助于在双端队列中定位或放置元素。

score 3 · Accepted Answer

好问题。

查看代码：

正如您所说，容量始终是二的幂。此外，永远不允许双端队列达到容量。

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    /**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other....

“二的幂”约定简化了“初始大小”：

 /**
  * Allocates empty array to hold the given number of elements.
  *
  * @param numElements  the number of elements to hold
  */
 private void allocateElements(int numElements) {
     int initialCapacity = MIN_INITIAL_CAPACITY;
     // Find the best power of two to hold elements.
     // Tests "<=" because arrays aren't kept full.
     if (numElements >= initialCapacity) {
         initialCapacity = numElements;
         initialCapacity |= (initialCapacity >>>  1);
         initialCapacity |= (initialCapacity >>>  2);
         initialCapacity |= (initialCapacity >>>  4);
         initialCapacity |= (initialCapacity >>>  8);
         initialCapacity |= (initialCapacity >>> 16);
         initialCapacity++;

         if (initialCapacity < 0)   // Too many elements, must back off
             initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
     }

最后，注意“掩码”的使用：

 /**
  * Removes the last occurrence of the specified element in this
  * deque (when traversing the deque from head to tail).
  * If the deque does not contain the element, it is unchanged.
  * More formally, removes the last element {@code e} such that
  * {@code o.equals(e)} (if such an element exists).
  * Returns {@code true} if this deque contained the specified element
  * (or equivalently, if this deque changed as a result of the call).
  *
  * @param o element to be removed from this deque, if present
  * @return {@code true} if the deque contained the specified element
  */
 public boolean removeLastOccurrence(Object o) {
     if (o == null)
         return false;
     int mask = elements.length - 1;
     int i = (tail - 1) & mask;
     Object x;
     while ( (x = elements[i]) != null) {
         if (o.equals(x)) {
             delete(i);
             return true;
         }
         i = (i - 1) & mask;
     }
     return false;
 }

 private boolean delete(int i) {
     checkInvariants();
     ...
     // Invariant: head <= i < tail mod circularity
     if (front >= ((t - h) & mask))
         throw new ConcurrentModificationException();
     ...
     // Optimize for least element motion
     if (front < back) {
         if (h <= i) {
             System.arraycopy(elements, h, elements, h + 1, front);
         } else { // Wrap around
             System.arraycopy(elements, 0, elements, 1, i);
             elements[0] = elements[mask];
             System.arraycopy(elements, h, elements, h + 1, mask - h);
         }
         elements[h] = null;
         head = (h + 1) & mask;

java - 为什么 Deque (ArrayDeque) 容量是 2 的幂？

4 回答 4

Related

Reference