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

EN

有一个内部调用Arrays.sort()的方法Collections.sort()。这使用合并排序来排序顺序为O(nlogn)的数据。还有一条信息是，如果要排序的元素数量小于7，则使用插入排序。

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

索引值get()- O(1) Object

• (

)- pos，Object

• )- O(n)

-O(N)

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

在Java Collections中，特别是在列表中，通常会对其两个具体实现ArrayList和LinkedList进行比较。LinkedList的顺序如下。

对象get()- O(n)

(

• )- O(1) (前提是在链接的list)
• insertAt(int pos中维护现成的最后一个指针，对象值)- O(n)
• remove(Object) -O(N)

集合实现类完全按照它们的数据结构命名。因此，HashSet和HashMap使用散列作为底层数据结构，而TreeSet和TreeMap使用二叉树。

更多信息可在这些类的JavaDoc中找到。例如，对于TreeSet，它说明：

此实现为基本操作(添加、删除和包含)提供了有保证的log(n)时间开销。

关于订单，我发现了一些有用的东西：

我发现下面的帖子对于大O符号非常有用：Big-O summary for Java Collections Framework implementations?

准确地说，在下面的网页http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/

下面是每个集合http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html上的实验结果的详细信息