基本Java容器的CRUD操作的渐进复杂度是什么？

Question

我正在尝试弄清楚Java基本集合操作的复杂度（使用大O符号）。类似于这个问题关于C++语言。

以下是我所知道的，根据常识：

列表

ArrayList

• add(E e) O(1)
• add(int index, E e) O(n)
• set(int index, E element) O(1)
• get(int index) O(1)
• remove(E e) remove(int index) O(n)
• contains(E e) O(n)
• list concatenation (addAll) O(n)

LinkedList

• add(E e) O(1) 添加元素
• add(int index, E e) O(n) 在指定位置插入元素
• set(int index, E element) O(n) 修改指定位置的元素
• get(int index) O(n) 获取指定位置的元素
• remove(E e) remove(int index) O(n) 删除指定元素或位置的元素
• contains(E e) O(n) 判断是否包含指定元素
• list concatenation (addAll) O(1) 链表合并

---

集合

HashSet和LinkedHashSet

• add(E e) O(1)（常数时间复杂度）
• remove(E e) O(1)（常数时间复杂度）
• contains(E e) O(1)（常数时间复杂度）
• 使用迭代器查找/获取元素 O(n)（线性时间复杂度）

TreeSet

• add(E e) O(log n)（对数时间复杂度）
• remove(E e) O(log n)（对数时间复杂度）
• contains(E e) O(log n)（对数时间复杂度）
• addAll O(n log n)（n乘以对数时间复杂度）
• 使用迭代器查找元素 O(n)（线性时间复杂度），或者实现二分查找可达到 O(log n)（对数时间复杂度）

---

地图

HashMap和LinkedHashMap

• put(K key, V value) O(1)
• get(K key) O(1)
• remove(E e) O(1)
• containsKey(Object key) O(1)
• containsValue(Object value) O(n)
• putAll O(n)
• 使用迭代器查找/获取元素 O(n) 或者可能是 O(log n)，与TreeSet相同

TreeMap

• put(K key, V value) O(log n)
• get(K key) O(log n)
• remove(E e) O(log n)
• containsKey(Object key) O(log n)
• containsValue(Object value) O(n)
• putAll O(n log n)
• 使用迭代器查找/获取元素 O(n)

<注意：基于哈希的集合假设有良好设计的哈希函数，时间复杂度为O(1)，否则为O(n)

问题： 这个说法正确吗？

- Jiri Kremser

---

ArrayList.Add(E e) 的摊销常数时间是恒定的。 - MAV

@MAV 对于很多“add”操作来说，这不是很正确吗？（我的意思是，不仅仅是ArrayList中提到的那些） - keyser

@Kᴇʏsᴇʀ 很可能是这样。我还没有阅读所有提到的集合的文档。 - MAV

-1 这个问题让我感到困扰，因为它基本上等同于“我懒得读文档，有人能读一下我的版本并告诉我是否正确吗？”我思考了一段时间关于这个负评，但最终完全缺乏任何研究推动了我。如果这个问题是关于特定集合的，引用文档并不确定其中一个方面，那就是另一回事；但这个问题可以通过从javadocs中复制粘贴来回答（正如它所证明的那样），这使得它成为一个相当糟糕的研究问题。 - yshavit

@yshavit，您建议创建6个不同的问题吗？这里的附加价值在于将所有内容放在一个问题中。我知道“我是对的”这种问题对SO来说很糟糕，但我不知道该如何用其他方式表达它。坦白地说，在SO上50％的Java问题可以通过复制和粘贴jdoc来回答。我没有注意到复杂性在jdoc中被提到（它们没有在方法部分中提到，而是在长描述中的顶部提到）。 - Jiri Kremser

Answer 1

关于这方面的最佳知识来源应该是文档。通过快速搜索，我找到了以下内容。

列表

ArrayList

size、isEmpty、get、set、iterator和listIterator操作在常数时间内运行。添加操作在均摊常数时间内运行，也就是说，添加n个元素需要O（n）的时间。所有其他操作都在线性时间内运行（粗略地说）。

LinkedList

所有操作的表现都符合双向链表的预期。索引列表的操作将从距离指定索引更近的开头或结尾遍历列表。

根据我对双向链表的记忆，我可以说你的“常识假设”是正确的。

集合

HashSet

这个类提供基本操作（添加、删除、包含和大小）的常数时间性能，假设哈希函数将元素适当地分散在桶中。对此集合进行迭代需要的时间与 HashSet 实例的大小（元素数量）加上支持 HashMap 实例（桶数量）的“容量”成比例。

LinkedHashSet

与 HashSet 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数将元素适当地分散在桶中。由于维护链表的额外开销，性能可能略低于 HashSet，但有一个例外：对 LinkedHashSet 进行迭代需要的时间与其大小成比例，而不管其容量如何。对 HashSet 进行迭代可能更昂贵，需要的时间与其容量成比例。

TreeSet

这个实现保证基本操作（添加、删除和包含）的时间复杂度为对数级别。

映射

HashMap

这个实现在哈希函数正确分散元素到桶中的情况下，提供常数时间的性能表现（获取和插入）。对集合视图进行迭代需要的时间与 HashMap 实例的“容量”（桶的数量）加上其大小（键值映射的数量）成正比。

LinkedHashMap

与 HashMap 类似，它在哈希函数正确分散元素到桶中的情况下，提供常数时间的性能表现（添加、包含和删除）。性能可能略低于 HashMap，...

TreeMap

这个实现提供了 containsKey、get、put 和 remove 操作的对数时间复杂度保证。

如果有些方法没有提到，请尝试查找该特定方法。如果文档中没有提到运行时间，那么它可能是实现相关的。

- MAV