Java集合addAll的复杂度

Question

有没有一个时间复杂度为O(1)而不是O(n)的Java集合可用于addAll操作？还是我必须自己实现集合？使用高效的链表，Collection1.addAll(Collection2) 操作应该将第二个集合附加到第一个集合，将collection2的第一个节点添加到collection1的最后一个节点，其余节点依次跟随。但是，从文档中阅读到的并不是这样，似乎它使用了迭代器，所以我猜测其复杂度为O(collection2.size)。

这样对吗？

- kaizokun

---

https://dev59.com/HGw15IYBdhLWcg3wi8dv - Jordi Castilla

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Sanjeev

Answer 1

即使是对链表的优化也只能在将项目从一个链表移动到另一个链表时才能起作用。

但是，您可以构建一种具有更高间接性级别的集合，即包含一个集合的集合。这样，添加整个集合非常便宜，迭代也很便宜。然而，索引或长度确定可能会变得非常昂贵。

- glglgl

---

当然，这真的取决于具体情况。对于长度的确定，我认为简单地将两个尺寸相加即可完成任务。谢谢。 - kaizokun

@Kaizokun 如果只有两个的话，也许如果你设计这个类具有最大的灵活性，它会更多。 - glglgl

当然，每次我添加一个集合时，我都会累加大小 :) - kaizokun

Answer 2

在这方面，ArrayList可能是最好的选择，但实际上它也取决于提供的集合。最优情况下的复杂度是O(1)，但前提是提供的集合的toArray()方法也具有常数复杂度。

执行实际分配的System.arrayCopy()调用无论如何都是O(1)很复杂，请参见下文：

// java.util.ArrayList.addAll
// Oracle JDK 1.8.0_91
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray(); // O(?) <-- depending on other type
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew); 
    size += numNew;
    return numNew != 0;
}

关于System.arrayCopy是否是常量时间操作存在一些争议。有人说不是。其他人则认为是。

根据我编写的基准测试，它处于中间水平。复制时间在大约100个数组项之前保持相当稳定，但从那时起呈线性增长，我猜测其中涉及某种分页。因此，实际上，除非数组很小，否则System.arrayCopy具有线性时间复杂度。

- Sean Patrick Floyd

---

谢谢你。在我的情况下，集合是一个链表（一种我不知道如何用英语说的链式列表），因此toArray操作的时间复杂度应该是O(n)。 - kaizokun

你确定吗？https://dev59.com/WGw05IYBdhLWcg3wkik-声称有所不同。此外，我相当确定`ensureCapacityInternal`也是`O(N)`的。 - fabian

第一部分是宗教战争的源头，没错。但从Java的角度来看，这是一个原子操作。虽然有不同意见，但这个答案支持我的理论：https://dev59.com/BHE85IYBdhLWcg3wdDIM#2772176 - Sean Patrick Floyd

第二部分是错误的。ensureCapacityInternal 的最佳情况复杂度为 O(1)，最坏情况为 O(n)，但最佳和最坏情况的比率足够好，使线性方面可以忽略不计。 - Sean Patrick Floyd

System.arrayCopy没有O(1)的参数。它必须循环每个数组项才能将其复制。仅使用memmove并不能神奇地使其成为O(1)，因为尽管在Java中是单个指令，但memmove不是O(1)。如果从Java中调用任何C函数都是O(1)，那么您也可以说任何NP问题实际上都是O(1)：只需编写一个解决该问题的C函数并从Java中调用它！ - Oli