removeIf 实现细节

Question

我有一个小的实现细节问题，我在ArrayList::removeIf. 我不认为我可以简单地把它放在没有一些先决条件的情况下。

如此：实现基本是散装 remove，不像ArrayList::remove。一个例子应该让事情更容易理解。假设我有这个列表：

List<Integer> list = new ArrayList<>(); // 2, 4, 6, 5, 5
list.add(2);
list.add(4);
list.add(6);
list.add(5);
list.add(5); 

我想删除每个偶数元素。我可以：

Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    int elem = iter.next();
    if (elem % 2 == 0) {
         iter.remove();
    }
}

或者：

list.removeIf(x -> x % 2 == 0);

结果将是相同的，但实现却大不相同。由于iterator是 的视图，因此ArrayList每次调用时remove，底层ArrayList都必须处于“良好”状态，这意味着内部数组实际上会发生变化。同样，在每次调用 时remove，都会在System::arrayCopy内部进行调用。

在对比度removeIf上更聪明。由于它在内部进行迭代，因此可以使事情更加优化。它这样做的方式很有趣。

它首先计算应该从中删除元素的索引。这是通过首先计算一个 tiny 来完成的，这是BitSet一个long值数组，其中每个索引都驻留一个64 bit值 (a long)。多个64 bit值使其成为BitSet. 要在特定偏移量处设置值，首先需要找出数组中的索引，然后设置相应的位。这不是很复杂。假设您想设置第 65 位和第 3 位。首先我们需要一个long [] l = new long[2]（因为我们超出了 64 位，但不超过 128 位）：

|0...(60 more bits here)...000|0...(60 more bits here)...000|

您首先找到索引：（65 / 64他们实际上是这样做的65 >> 6），然后在该索引 ( 1) 中放置所需的位：

1L << 65 // this will "jump" the first 64 bits, so this will actually become 00000...10. 

同样的事情3。因此，长数组将变为：

|0...(60 more bits here)...010|0...(60 more bits here)...1000|

在源代码中，他们称之为 BitSet - deathRow（好名字！）。

---

让我们even在这里举个例子，其中list = 2, 4, 6, 5, 5

• 他们迭代数组并计算它deathRow（其中Predicate::test是true）。

死亡行 = 7 (000 ... 111)

意味着索引 = [0, 1, 2] 将被删除

• 他们现在根据该 DeathRow 替换底层数组中的元素（不详细说明这是如何完成的）

内部数组变为：[5, 5, 6, 5, 5]。基本上，它们移动应该保留在数组前面的元素。

---

我终于可以提出问题了。

此时，他们知道：

 w   ->  number of elements that have to remain in the list (2)
 es  ->  the array itself ([5, 5, 6, 5, 5])
 end ->  equal to size, never changed

对我来说，这里只需要一步：

void getRidOfElementsFromWToEnd() {
    for(int i=w; i<end; ++i){
       es[i] = null;
    }
    size = w;
}

相反，会发生这种情况：

private void shiftTailOverGap(Object[] es, int w, int end) {
    System.arraycopy(es, end, es, w, size - end);
    for (int to = size, i = (size -= end - w); i < to; i++)
        es[i] = null;
}

我在这里故意重命名了变量。

打电话有什么意义：

 System.arraycopy(es, end, es, w, size - end);

特别是size - end，因为一直end 是 size- 它永远不会改变（所以总是如此zero）。这在这里基本上是一个NO-OP。我在这里错过了什么角落案例？

Answer 1

您正在查看您调用的列表removeIf与ArrayList. 只有在这种情况下，您才能假设end始终等于size。

一个反例是：

ArrayList<Integer> l = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
l.subList(2, 5).removeIf(i -> i%2 == 1);

同样，removeAll将shiftTailOverGap使用一个end参数调用，该参数可能与size应用于subList.

调用 时会出现类似的情况clear()。在这种情况下，在调用它ArrayList本身时执行的实际操作是如此微不足道，以至于它甚至不调用该shiftTailOverGap方法。只有在使用类似的东西时l.subList(a, b).clear()，它才会结束在removeRange(a, b)on l，反过来，正如你自己已经发现的那样，调用shiftTailOverGap(elementData, a, b)一个b可以小于size.