4

正如我看到的源代码:java.util.AbstractCollection.toArray(),它是这样实现的:

 public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // overflow-conscious code
            if (newCap - MAX_ARRAY_SIZE > 0)
                newCap = hugeCapacity(cap + 1);
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // trim if overallocated
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

如您所见,实现并不容易理解,我的问题是:

  1. 当集合的元素在迭代过程中发生变化(大小不变)时,我会得到什么?我猜迭代器可能是某种快照。
  2. 当集合的大小改变时我会得到什么?我想知道它是否可以正常工作。
4

4 回答 4

3

如您所见,实现并不容易理解,我的问题是:

  1. 当集合的元素在迭代过程中发生变化(大小不变)时,我会得到什么?我猜迭代器可能是某种快照。
  2. 当集合的大小改变时我会得到什么?我想知道它是否可以正常工作。

实现方式就是这样,因为它旨在处理迭代器返回的元素数量与size(). 如果集合的大小在迭代期间发生变化,则可能会发生这种情况。目标数组是基于 分配的size(),在大小不变的乐观情况下,它非常简单。代码的复杂性在于迭代器返回的实际元素数量与返回的初始值不同size()。如果元素的实际数量较小,则将元素复制到较小的正确大小的数组中。如果实际数字更大,则将元素复制到更大的数组中,然后迭代更多元素。如果数组填满,则数组会重复重新分配更大,直到迭代完成。

对于您的第一个问题,迭代器不一定拍摄元素的快照。这取决于实际的集合实现。某些集合(例如CopyOnWriteArrayList)确实具有快照语义,因此如果修改了集合,则该修改对迭代器不可见。在这种情况下,迭代器报告的元素数量将匹配size(),因此不需要重新分配数组。

如果集合在迭代期间被修改,其他集合实现有不同的策略。有些是快速失败的,这意味着他们会抛出ConcurrentModificationException. 其他是弱一致的,这意味着修改可能对迭代器可见,也可能不可见。

这适用于你的第二个问题。如果集合大小在迭代期间发生变化,并且该集合的迭代器支持这一点(即,它不是快速失败的),则此处的代码将处理来自迭代器的元素数量与最初报告的不同size()

可能发生这种情况的一个例子是ConcurrentSkipListSet. 这个类的迭代器是弱一致的,它继承toArray()AbstractCollection. 因此,在toArray()迭代集合以将元素收集到目标数组中时,另一个线程修改集合是完全合法的,可能会改变它的大小。这显然会导致迭代器报告与返回的初始值不同数量的元素size(),这将导致执行数组重新分配代码toArray()

于 2016-01-08T02:36:34.707 回答
0

当集合的大小发生变化时,我会得到什么?

  • 如果集合的大小小于预期,则使用注释指示的return Arrays.copyOf(r, i)intoArray()方法“减少”数组。
  • 如果集合的大小超出预期,it.hasNext() ? finishToArray(r, it) : r调用会处理这种情况。finishToArray方法继续将元素添加到数组中,并在需要时“扩展”其大小:计算新容量 ( newCap = cap + (cap >> 1) + 1) 并“扩展”数组 ( r = Arrays.copyOf(r, newCap))。
于 2016-01-07T15:09:51.560 回答
0

我不认为所有的 Collection 实现都是线程安全的,而不用担心你可以让你的 Collection 同步使用:

Collections.synchronizedCollection(myCollection);

或者你可以看看:

https://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html

编辑: 在这里我找到了一个很好的解释

于 2016-01-07T15:13:48.027 回答
0

您只能确定迭代的结果是未定义的(除非您知道正在使用的集合的确切实现)。通常ConcurrentModificationException会抛出 a ,但你不能依赖这个假设。

如果Collection在迭代它时修改了 a,在大多数实现中,ConcurrentModificationException都会抛出 a。Iterators这样做被称为快速失败的迭代器。

但这取决于每个实现,尽管 JRE 提供的所有通用集合实现都这样做,但并非所有实现Iterators都是快速失败的。还要注意,不能保证快速失败的行为,因为一般来说,在存在不同步的并发修改的情况下,不可能做出任何硬保证。

为什么toArray在java中是这样实现的?

因为这个实现假设集合的大小可以随时改变,因为迭代器可能不会抛出任何异常。因此,此方法检查迭代器是否可以提供比初始估计大小更多或更少的元素。

于 2016-01-07T16:33:37.473 回答