ArrayDeque 的 addFirst 方法 Class

Question

java.util.ArrayDequeclass中addFirst方法的代码为

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

在这里，我无法理解

的意思

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

此外，假设数组大小为10。头在0，尾在9（数组已满）。在这种情况下，插入什么索引系统？（我的理解是：如果数组已满，则先增加其大小，然后在 arraySize()-1 索引中插入。）

Answer 1

以下行的功能基本上是(head - 1) MODULO (elements.length)，因此当head == 0.

时，从head减去1得到最大可能值而不是-1

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

10 不是 elements 的有效长度，根据实现，elements.length 始终是 2 的幂。如果不是这种情况，操作将无法进行。

理解为什么这行得通需要位运算的知识。假设 elements.length == 16 == 00010000b 并且为了简单起见，值的长度是 8 位而不是实际的 32 位：

(elements.length - 1) 用于获取 n 位长的位掩码，其中 2^n 是元素的当前长度。 (elements.length - 1) == 15 == 00001111b 在这种情况下。

如果 head > 0 和 head < elements.length（给定的），则 (head - 1) & (elements.length - 1) == (head - 1)，因为 ANDing 与 1 什么都不做。

如果head == 0，head - 1 == -1 == 11111111b。（二进制补码有符号整数表示法，尽管您也可以将其视为简单的整数溢出。）与掩码 (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15 进行与操作，这是想要的值。

Answer 2

这里它使用 & 运算符意味着它将对两个整数执行二进制 AND 运算。

让我们假设你的案例 head = 0 那么 head 将变成

头 = -1

和 elements.length = 16（默认情况下，正如@Adrian 所说，它只会是 2 的幂）

所以执行操作-1 & 15（即11111111 & 00001111）它将变成15，这是添加元素的目标位置。

ArrayDeque 的 addFirst 方法 Class

addFirst method of ArrayDeque Class

java

arraydeque