In Java (but similarly in PHP) the ArrayDeque implementation always has its capacity as a power of 2:
For HashMap this choice is clear - to have a uniform element distribution based on a trimmed 32-bit hash. But Deque inserts/removes elements sequentially.
Also, ArrayList doesn't restrict its capacity to a power of two, just ensures it's at least the number of elements.
So, why does the Deque implementation require its capacity to be a power of 2?
I guess, for performance reasons. For example, let's look at implementation of addLast function:
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
So, instead of tail = (tail + 1) % elements.length it is possible to write tail = (tail + 1) & (elements.length - 1) (& works faster, than %). Such constructions are used many times in ArrayDeque's source code.
Finally i found it!!!
The reason not just in performance and bits-mask operations (yes, they are faster, but not significantly). The real reason is to allow loop back the elements capacity if we use sequential adding-removing operations. In other words: reuse released cells after remove() operation.
Consider the following examples (initial capacity is 16):
Only add():
add 15 elements => head=0, tail=15
add more 5 elements => doubleCapacity() => head=0, tail=20, capacity=32
add()-remove()-add():
add 15 elements => head=0, tail=15
remove 10 elements => tail loops back to removed indexes => head=10, tail=15
add more 5 elements => the capacity remains 16, the elements[] array is not rebuilt or reallocated! => new elements are added into the place of the removed elements to the beginning of the array => head=10, tail=4 (looped back to the start of the array from 15->0->1->2->3->4). Note the values 16-19 are inserted to the indexes 0-3
So, in this case using power of two and concise bit operations makes much more sense. With such approach the operations like if ( (tail = (tail + 1) & (elements.length - 1)) == head) allow to assign and verify easily that the looped tail does not overlap with the head (yeah, the stupid snake where actually the tail bites the head :) )
The code snippet to play around:
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();
Powers of 2 lend themselves to certain masking operations. For example to get the lower order number of bits from an integer.
so if the size is 64, then 64-1 is 63 which is 111111 in binary.
This facilitates locating or placing elements within the deque.
Good question.
Looking in the code:
As you said, the capacity is always a power of two. Furthermore, the deque is never allowed to reach capacity.
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....
The "power of two" convention simplifies "initial size":
/**
* 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
}
Finally, note the use of "mask":
/**
* 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;
