addFirst metoda ArrayDeque klasy

Question

Kodeksu metody addFirst w klasie java.util.ArrayDeque jest

public void addFirst(E e) { 
    if (e == null) 
     throw new NullPointerException(); 
    elements[head = (head - 1) & (elements.length - 1)] = e; 
    if (head == tail) 
     doubleCapacity(); 
} 

Tutaj nie jestem w stanie zrozumieć sens

head = (head - 1) & (elements.length - 1) 

Załóżmy także, jeśli rozmiar tablicy to 10. Głowa ma wartość 0, a ogon ma wartość 9 (tablica jest pełna). W takim przypadku, w jakim systemie indeksu będzie wstawiać? (Rozumiem, że jeśli tablica jest pełna, najpierw zwiększ jej rozmiar, a następnie wstaw w indeks arraySize() -1).

Answer 1

Funkcjonalność poniższej linii to w zasadzie (head - 1) MODULO (elements.length), więc odjęcie 1 od głowy daje maksymalną możliwą wartość zamiast -1, gdy head == 0.

head = (head - 1) & (elements.length - 1) 

10 nie jest ważna długość elements, odpowiednio do implementacji, elements.length zawsze jest potęgą dwójki. Gdyby tak nie było, operacja nie działałaby.

Zrozumienie, dlaczego to działa, wymaga znajomości operacji bitowych. Zakładając elements.length == 16 == 00010000b i długość wartości jest 8 bitów, zamiast rzeczywistego 32, w celu uproszczenia:

(elements.length - 1) jest wykorzystywana przez maskę bitu oprócz N bitów, gdzie 2^N to długość elementów. (elements.length - 1) == 15 == 00001111b w tym przypadku.

Jeśli head > 0 i head < elements.length (który jest podany), to (head - 1) & (elements.length - 1) == (head - 1), jak AND z 1s nic nie robi.

Jeśli head == 0, head - 1 == -1 == 11111111b. (Dopełnienie dwuznaczne ze znakiem całkowitoliczbowym, chociaż można go również postrzegać jako zwykłe przepełnienie całkowite.) ORAZ z maską (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15, która jest pożądaną wartością.

Answer 2

Tutaj jego użycie operatora & oznacza, że ​​wykona operację Binary AND zarówno w liczbie całkowitej.

pozwala zakładać sprawa głowa = 0 wtedy głowa będzie

głowa = -1

i elements.length = 16 (która jest domyślnie, a także jako @Adrian powiedział, że będzie mieć tylko moc z 2)

więc wykonanie operacji -1 & 15 (tj. 11111111 & 00001111) stanie się 15, która jest docelową pozycją, aby dodać element.