ArrayDeque类的addFirst方法 [英] addFirst method of ArrayDeque Class

问题描述

java.util.ArrayDeque类中addFirst方法的代码是

The code of addFirst method in java.util.ArrayDeque class is

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. head为0且tail是9（数组已满）。在这种情况下，什么索引系统会插入？
（我的理解是：如果数组已满，则首先增加其大小，然后在arraySize（） - 1索引中插入。）

Also, Suppose if array size is 10. head is at 0 and tail is at 9(Array is full). In this case, at what index system will do insertion? (My understanding is: if array is full then, first increase its size and then do insertion in the arraySize()-1 index.)

推荐答案

以下行的功能基本上是（head-1）MODULO（elements.length），所以从头部减1会导致 head == 0 时的最大可能值而不是-1。

The functionality of the following line is basically (head - 1) MODULO (elements.length), so that subtracting 1 from head results in the maximum possible value instead of -1 when head == 0.

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

10是元素的有效长度，根据实现， elements.length 总是2的幂。如果不是这种情况，则操作不起作用。

10 is not valid length of elements, according to the implementation, elements.length is always a power of two. If this were not the case the operation would not work.

理解为什么这样做需要比特操作的知识。
假设 elements.length == 16 == 00010000b 并且为了简单起见，值的长度是8位而不是实际的32：

Understanding why this works requires knowledge of bit operations. Assuming elements.length == 16 == 00010000b and that the length of values are 8 bits instead of the actual 32 for simplicity's sake:

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

(elements.length - 1) is used to get a bit mask of ones n bits long, where 2^n is the current length of elements. (elements.length - 1) == 15 == 00001111b in this case.

如果头> 0 和 head< elements.length （这是给定的），然后是（head-1）& （elements.length - 1）==（head - 1），因为与1s的AND运不起作用。

If head > 0 and head < elements.length (which is a given), then (head - 1) & (elements.length - 1) == (head - 1), as ANDing with 1s does nothing.

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

If head == 0, head - 1 == -1 == 11111111b. (Two's complement signed integer notation, although you can also view it as a simple integer overflow.) ANDing with the mask (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15, which is the wanted value.

这篇关于ArrayDeque类的addFirst方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！