Почему емкость Deque (ArrayDeque) равна двум?

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 не ограничивает свою емкость степенью двойки, а только обеспечивает, по крайней мере, количество элементов.

Итак, почему для реализации 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.

Answer 2

Наконец я нашел это !!! Причина не только в производительности и операциях с битовой маской (да, они быстрее, но незначительно). Реальная причина в том, чтобы разрешить возврат назад elements емкость, если мы используем последовательные операции добавления-удаления . Другими словами: повторно использовать освобожденные ячейки после операции remove().

Рассмотрим следующие примеры (начальная емкость 16 ):

1. Только add():

   1. добавить 15 элементов => голова = 0, хвост = 15

   2. добавить еще 5 элементов => doubleCapacity() => голова = 0, хвост = 20, емкость = 32

   

2. 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();

Answer 3

Хороший вопрос.

Глядя в коде:

1. Как вы сказали, емкость всегда является степенью двойки. Кроме того, деку никогда не разрешается достигать емкости.

   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....
   

2. Соглашение "степень двух" упрощает "начальный размер":

    /**
     * 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
        }
   

3. Наконец, обратите внимание на использование «маски»:

    /**
     * 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;
   

Answer 4

Способности 2 поддаются определенным маскировочным операциям.Например, чтобы получить младшее число битов из целого числа.

, поэтому если размер равен 64, то 64-1 равен 63, что равно 111111 в двоичном формате.

Это облегчает поиск или размещениеэлементы внутри deque.