Warum verwendet die ArrayDeque-Klasse die bitweise Operation in der pollFirst-Methode?

Question

Ich schaue durch Java-Quellcode versuchen, die Implementierung der Sammlung zu lernen. Eine interessante Sache in der ArrayDeque-Klasse gefunden.

public E pollFirst() { 
    int h = head; 
    @SuppressWarnings("unchecked") 
    E result = (E) elements[h]; 
    // Element is null if deque empty 
    if (result == null) 
     return null; 
    elements[h] = null;  // Must null out slot 
    head = (h + 1) & (elements.length - 1); 
    return result; 
} 

public E pollLast() { 
    int t = (tail - 1) & (elements.length - 1); 
    @SuppressWarnings("unchecked") 
    E result = (E) elements[t]; 
    if (result == null) 
     return null; 
    elements[t] = null; 
    tail = t; 
    return result; 
} 

Was bedeuten die folgenden 2 Zeilen? Ist es eine bitweise Operation? Warum benutzen sie es und was ist der Zweck hier?

Ich weiß, ein Szenario, das bitweise zu verwenden ist, um 2 Werte in 1 Variable zu packen. Aber das scheint nicht der Fall zu sein. -

Answer 1

einen Blick auf den Code Initialisierung Nehmen Sie die Deque ist als eine Anordnung, deren Größe immer eine Potenz von 2 dargestellt wird:

195 public ArrayDeque(int numElements) { 
196  allocateElements(numElements); 
197 } 

124 private void allocateElements(int numElements) { 
125  int initialCapacity = MIN_INITIAL_CAPACITY; 
126  // Find the best power of two to hold elements. 
127  // Tests "<=" because arrays aren't kept full. 
128  if (numElements >= initialCapacity) { 
129   initialCapacity = numElements; 
130   initialCapacity |= (initialCapacity >>> 1); 
131   initialCapacity |= (initialCapacity >>> 2); 
132   initialCapacity |= (initialCapacity >>> 4); 
133   initialCapacity |= (initialCapacity >>> 8); 
134   initialCapacity |= (initialCapacity >>> 16); 
135   initialCapacity++; 
136 
137   if (initialCapacity < 0) // Too many elements, must back off 
138    initialCapacity >>>= 1;// Good luck allocating 2^30 elements 
139  } 
140  elements = (E[]) new Object[initialCapacity]; 
141 } 

so ist elements.length - 1 binär ist im Grunde eine Reihe von 1 Bits vor der Größe Das Array ist überschritten.

Wenn beispielsweise elements mit einem Array der Größe 16 initialisiert wird, ist elements.length - 1 15, was 0..001111 bedeutet (abgeschnittene führende Nullen).

Wenn also das head Element in pollFirst Methode (um eins erhöht) zurückgesetzt wird, wird der bitweise Operator & verwendet, um die Deque zyklisch zu machen. Noch einmal, wenn elements der Größe 16 ist und zur Zeit head ist 15, dann wäre head + 1 16 Jahre alt sein, und so:

10000 
01111 
----- 
00000 

Bedeutung ist die head zurückgesetzt Index 0. Auf diese Weise können Sie den Raum Sie haben wieder zu verwenden bereits zugewiesen, wobei das Array und seine O (1) -Effizienz beim Einfügen und Abrufen verwendet wird, ohne dass neuer Speicherplatz zugewiesen werden muss.

Das gleiche gilt für pollLast, wo Sie die tail Variable zurückgesetzt, dh wenn tail 0 und elements der Größe 16 ist, dann:

tail  00000 
tail-1 11111 (-1 in two's complement) 
      01111 
      ----- 
      01111 

tail Bedeutung ist ein Wert erniedrigt, sondern bewegt sich von 0 bis elements.length - 1.

Sie hätten dasselbe mit einer komplexeren if-Anweisung (oder mit dem trinary-Operator) erreichen können, dies ist jedoch eine ziemlich übliche und akzeptable Methode zur Implementierung eines zyklischen Arrays.

Answer 2

Es ist ein effizienter Weg (head+1) % elements.length der Berechnung, was wir tun können, weil elements.length eine Potenz von 2 ist es effizienter ist, weil der mod Operator bitweise und teuer im Vergleich ist.

Am anderen Ende, nur mit mod für die tail würde nicht funktionieren, weil in Java, -1 % N == -1.