java - 什么是基本 Java 容器上的 CRUD 操作的渐近复杂度

Question

我试图找出 Java 基本集合操作的复杂性(使用 big-o 表示法)。与此类似 question用于 C++ 语言。

根据常识，这是我所拥有的:

列表

数组列表

• 添加(E e) O(1)
• add(int index, E e) O(n)
• set(int 索引, E 元素 O(1)
• 获取(整数索引)O(1)
• 移除(E e) 移除(int index) O(n)
• 包含(E e) O(n)
• 列表连接(addAll)O(n)

链表

• 添加(E e) O(1)
• add(int index, E e) O(n)
• set(int 索引, E 元素 O(n)
• get(int 索引) O(n)
• 移除(E e) 移除(int index) O(n)
• 包含(E e) O(n)
• 列表串联(addAll)O(1)

---

集

HashSet 和 LinkedHashSet

• 添加(E e) O(1)
• 删除(E e) O(1)
• 包含(E e) O(1)
• 使用迭代器查找/获取元素 O(n)

树集

• 添加(E e) O(log n)
• 删除(E e) O(log n)
• 包含(E e) O(log n)
• addAll O(n log n)
• 使用迭代器 O(n) 或 O(log n) 在实现二分查找时找到一个元素

---

map

HashMap 和 LinkedHashMap

• put(K key, V value) O(1)
• 得到(K 键)O(1)
• 删除(E e) O(1)
• containsKey(对象键)O(1)
• 包含值(对象值)O(n)
• putAll O(n)
• 使用迭代器 O(n) 或 O(log n) 查找/获取元素，与 TreeSet
相同

TreeMap

• put(K key, V value) O(log n)
• get(K 键) O(log n)
• 删除(E e) O(log n)
• containsKey(对象键) O(log n)
• 包含值(对象值)O(n)
• putAll O(n log n)
• 使用迭代器查找/获取元素 O(n)

注意:基于散列的集合假定设计良好的散列函数在 O(1) 中，否则在 O(n) 中

问题:这是正确的吗？

Answer 1

您最好的知识来源是文档。这是我可以通过一两次快速搜索找到的内容。

列表

ArrayList

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

LinkedList

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

根据我对双向链表的内存，我会说你的“常识性假设”是正确的。

集

HashSet

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets).

LinkedHashSet

Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

TreeSet

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

map

HashMap

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

LinkedHashMap

Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap,...

TreeMap

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

如果没有提到某些方法，请尝试查找该具体方法。如果文档中的任何地方都没有提到运行时间，它可能取决于实现。