为什么 ArrayDeque class 在 pollFirst 方法中使用按位操作?
Why the ArrayDeque class use bitwise operation in the pollFirst method?
我查看java源代码尝试学习集合的实现。
在 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;
}
下面两行是什么意思?
是位运算吗?他们为什么使用它,目的是什么?
head = (h + 1) & (elements.length - 1);
int t = (tail - 1) & (elements.length - 1);
我知道使用按位的一种情况是将 2 个值打包到 1 个变量中。但似乎并非如此。
看一下初始化代码——双端队列表示为一个数组,其大小始终是 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 }
所以 elements.length - 1
是二进制,基本上是超出数组大小之前的一系列 1
位。
例如,如果 elements
初始化为大小为 16 的数组,则 elements.length - 1
为 15,即 0..001111
(截断前导零)。
因此,当 head
元素在 pollFirst
方法中重置时(前进一),按位 &
运算符用于使 Deque 循环。同样,如果 elements
的大小为 16,而当前 head
为 15,则 head + 1
将为 16,因此:
10000
01111
-----
00000
意思是,head
被重置为索引 0。这允许您重用已经分配的 space,使用数组及其 O(1) 的插入和检索效率, 无需分配新的 space.
对于 pollLast
也是如此,您重置 tail
变量,即如果 tail
为 0 并且 elements
的大小为 16,则:
tail 00000
tail-1 11111 (-1 in two's complement)
01111
-----
01111
意思是tail
减了一个值,但是从0移动到elements.length - 1
。
您可以使用更多 "complex" if 语句(或使用三元运算符)实现相同的效果,但这是实现循环数组的一种相当普遍且可接受的方式。
这是一种更有效的计算 (head+1) % elements.length
的方法,我们可以这样做,因为 elements.length
是 2 的幂。它更有效,因为 mod 运算符与 按位和 相比开销较大。
另一方面,仅对 tail
使用 mod 是行不通的,因为在 Java、-1 % N == -1
中.
我查看java源代码尝试学习集合的实现。 在 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;
}
下面两行是什么意思? 是位运算吗?他们为什么使用它,目的是什么?
head = (h + 1) & (elements.length - 1);
int t = (tail - 1) & (elements.length - 1);
我知道使用按位的一种情况是将 2 个值打包到 1 个变量中。但似乎并非如此。
看一下初始化代码——双端队列表示为一个数组,其大小始终是 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 }
所以 elements.length - 1
是二进制,基本上是超出数组大小之前的一系列 1
位。
例如,如果 elements
初始化为大小为 16 的数组,则 elements.length - 1
为 15,即 0..001111
(截断前导零)。
因此,当 head
元素在 pollFirst
方法中重置时(前进一),按位 &
运算符用于使 Deque 循环。同样,如果 elements
的大小为 16,而当前 head
为 15,则 head + 1
将为 16,因此:
10000
01111
-----
00000
意思是,head
被重置为索引 0。这允许您重用已经分配的 space,使用数组及其 O(1) 的插入和检索效率, 无需分配新的 space.
对于 pollLast
也是如此,您重置 tail
变量,即如果 tail
为 0 并且 elements
的大小为 16,则:
tail 00000
tail-1 11111 (-1 in two's complement)
01111
-----
01111
意思是tail
减了一个值,但是从0移动到elements.length - 1
。
您可以使用更多 "complex" if 语句(或使用三元运算符)实现相同的效果,但这是实现循环数组的一种相当普遍且可接受的方式。
这是一种更有效的计算 (head+1) % elements.length
的方法,我们可以这样做,因为 elements.length
是 2 的幂。它更有效,因为 mod 运算符与 按位和 相比开销较大。
另一方面,仅对 tail
使用 mod 是行不通的,因为在 Java、-1 % N == -1
中.