java - 实现集合及其顺序时使用的实际数据结构是什么？

Question

Java 中使用了不同的集合，如哈希表、哈希集、 vector 、树集、 TreeMap 和 HashMap 。它们在内部是如何实现的？这些集合实际使用的数据结构是什么？还有，什么是顺序？

如果我们稍微讨论一下集合的实现就好了。

Answer 1

有一个方法Collections.sort()，它在内部调用Arrays.sort()。这使用归并排序来对阶数为 O(nlogn) 的数据进行排序。还有一点是，如果要排序的元素数量小于7，则使用插入排序。

与 Vector 和 ArrayList 一样，以下是复杂性，因为它使用简单的数组

• 获取(索引) - O(1)
• 添加(对象) - O(n)
• insertAt(int pos, 对象值) - O(n)
• 删除(对象) - O(n)

还有一件事是，HashSet 内部使用 HashMap 只关心映射的键和被忽略或未使用的对象，因此不存在两种不同的实现。 HashMap 通过为每个对象生成唯一的哈希码来使用无冲突或理想哈希。因此，对于数据的插入和检索，顺序最好为 1。

在 Java 集合中，尤其是在列表中，通常会对其两个具体实现(ArrayList 和 LinkedList)进行比较。 LinkedList的顺序如下。

• 获取(索引) - O(n)
• add(Object) - O(1)(假设链表中维护有现成的最后一个指针)
• insertAt(int pos, 对象值) - O(n)
• 删除(对象) - O(n)