Albert Gao - 8 months ago 21

Java Question

I look through java source code try to learn the implementation of collection.

Found a interesting thing in the ArrayDeque class.

`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;

}

What does the following 2 lines mean?

Is it a bitwise operation? Why they use it and what's the purpose here?

`head = (h + 1) & (elements.length - 1);`

int t = (tail - 1) & (elements.length - 1);

I know one scenario to use the bitwise is to pack 2 values in 1 variable. But it seems this is not the case.

Answer

Take a look at the initialization code - the Deque is represented as an array whose size is always a power of 2:

```
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 `elements.length - 1`

is binary is basically a series of `1`

bits before the size of the array is exceeded.

For instance, if `elements`

is initialized to an array of size 16, then `elements.length - 1`

is 15, meaning `0..001111`

(truncated leading zeros).

So when the `head`

element is reset in `pollFirst`

method (advanced by one), the bitwise `&`

operator is used in order to make the Deque cyclic. Again, if `elements`

is of size 16 and currently `head`

is 15, then `head + 1`

would be 16, and so:

```
10000
01111
-----
00000
```

Meaning, the `head`

is reset to index 0. This allows you to reuse the space you've already allocated, using the array and its O(1) efficiency in inserting and retrieval, without needing to allocate new space.

The same is true for `pollLast`

where you reset the `tail`

variable, i.e. if `tail`

is 0 and `elements`

is of size 16, then:

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

Meaning `tail`

is decremented one value, but moves from 0 to `elements.length - 1`

.

You could have achieved the same with a more "complex" if statement (or by using the trinary operator), however this is a fairly common and acceptable way of implementing a cyclic array.