blocks|key|2495000|text|集合实现类完全按照它们的数据结构命名。因此，HashSet和HashMap使用散列作为底层数据结构，而TreeSet和TreeMap使用二叉树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2495001|更多信息可在这些类的JavaDoc中找到。例如，对于TreeSet，它说明：|offset|length|2495002|2495003|此实现为基本操作(添加、删除和包含)提供了有保证的log(n)时间开销。|blockquote|2495004|2495005|entityMap|0|LINK|mutability|MUTABLE|url|http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html^0|0|Q|7|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@$D|U|E|V|1|W]]|A|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|G|3|H|5|I|7|Y|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

The collections implementation classes are named exactly after their data structures. So HashSet and HashMap used a hash as the underlying data structure, while TreeSet and TreeMap use a binary tree.

More info is available in the JavaDoc of those classes. For example, for <a href="http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html" rel="nofollow noreferrer">TreeSet</a> it states: 

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

blocks|key|5872833|text|关于订单，我发现了一些有用的东西：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5872834|我发现下面的帖子对于大O符号非常有用：Big-O+summary+for+Java+Collections+Framework+implementations?|offset|length|5872835|准确地说，在下面的网页http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/|5872836|下面是每个集合http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html上的实验结果的详细信息|5872837|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations|1|http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/|2|http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html^0|0|J|1P|0|0|B|2J|1|0|7|28|2|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|F|3|G|5|6|7|10|8|@]|9|@$D|11|E|12|1|13]]|A|$]]|$1|H|3|I|5|6|7|14|8|@]|9|@$D|15|E|16|1|17]]|A|$]]|$1|J|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q]]|R|$5|M|N|O|A|$P|S]]|T|$5|M|N|O|A|$P|U]]]]

Related to Order I find something useful:

I found below post very useful in respect to Big O notation:
<a href="https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations">Big-O summary for Java Collections Framework implementations?</a>

and in precise below webpage
<a href="http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/" rel="nofollow noreferrer">http://simplenotions.wordpress.com/2009/05/13/java-standard-data-structures-big-o-notation/</a>

below details about experiment result on each collection
<a href="http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html" rel="nofollow noreferrer">http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html</a>

blocks|key|591214|text|您可能会找到这个illuminating。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|591215|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.virginia.edu/kim/publicity/pldi09tutorials/memory-efficient-java-tutorial.pdf^0|8|C|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You might find this <a href="http://www.cs.virginia.edu/kim/publicity/pldi09tutorials/memory-efficient-java-tutorial.pdf" rel="nofollow noreferrer">illuminating</a>.

blocks|key|583017|text|有一个内部调用Arrays.sort()的方法Collections.sort()。这使用合并排序来排序顺序为O(nlogn)的数据。还有一条信息是，如果要排序的元素数量小于7，则使用插入排序。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|583018|与Vector和ArrayList一样，下面是复杂性，因为它使用了一个简单的数组|583019|索引值get()-+O(1)+Object+|583020|(|unordered-list-item|583021|)-+pos，Object|583022|)-+O(n)+|583023|-O(N)|583024|583025|583026|另一件事是，HashSet在内部使用HashMap，只关心映射的键和被忽略或未使用的对象，因此没有两种不同的实现。HashMap通过为每个对象生成唯一的散列码来使用无冲突散列或理想散列。因此，对于数据的插入和检索，顺序最好是1。|583027|在Java+Collections中，特别是在列表中，通常会对其两个具体实现ArrayList和LinkedList进行比较。LinkedList的顺序如下。|583028|对象get()-+O(n)+|583029|583030|583031|)-+O(1)+(前提是在链接的list)|583032|insertAt(int+pos中维护现成的最后一个指针，对象值)-+O(n)+|583033|remove(Object)+-O(N)|583034|583035|583036|entityMap^0|7|D|N|I|0|1|6|8|9|0|0|0|1|1|1|1|0|6|7|I|7|0|12|9|1C|A|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1H|8|@$9|1I|A|1J|B|C]|$9|1K|A|1L|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1M|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|1N|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|1O|8|@]|D|@]|E|$]]|$1|O|3|P|5|L|7|1P|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1Q|8|@]|D|@]|E|$]]|$1|S|3|-4|5|L|7|1R|8|@]|D|@]|E|$]]|$1|T|3|-4|5|6|7|1S|8|@]|D|@]|E|$]]|$1|U|3|V|5|6|7|1T|8|@$9|1U|A|1V|B|C]|$9|1W|A|1X|B|C]]|D|@]|E|$]]|$1|W|3|X|5|6|7|1Y|8|@$9|1Z|A|20|B|C]|$9|21|A|22|B|C]]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|23|8|@]|D|@]|E|$]]|$1|10|3|-4|5|L|7|24|8|@]|D|@]|E|$]]|$1|11|3|K|5|6|7|25|8|@]|D|@]|E|$]]|$1|12|3|13|5|L|7|26|8|@]|D|@]|E|$]]|$1|14|3|15|5|L|7|27|8|@]|D|@]|E|$]]|$1|16|3|17|5|L|7|28|8|@]|D|@]|E|$]]|$1|18|3|-4|5|L|7|29|8|@]|D|@]|E|$]]|$1|19|3|-4|5|6|7|2A|8|@]|D|@]|E|$]]|$1|1A|3|-4|5|6|7|2B|8|@]|D|@]|E|$]]]|1B|$]]

There is this method <code>Collections.sort()</code> which internally calls <code>Arrays.sort()</code>. This uses the merge sort to sort data which has the order O(nlogn). And one more information is, if the number of elements to be sorted is lesser than 7, it uses the insertion sort.

As with <code>Vector</code> and <code>ArrayList</code> following are the complexities since it uses a simple array

<ul>
<li>get(index) - O(1) </li>
<li>add(Object) - O(n)</li>
<li>insertAt(int pos, Object value) - O(n) </li>
<li>remove(Object) - O(n)</li>
</ul>

One more thing is that <code>HashSet</code> internally uses a <code>HashMap</code> only worrying about the keys of a map and the objects being ignored or unused so that there are no two different implementations. And HashMap uses the collision free or the ideal hashing by generating unique hashcodes for every object. So, the order would be ideally 1 for insertion and retrieval of data. 

Often in Java Collections, especially in Lists, there is this usual comparison between its two concrete implementations, the <code>ArrayList</code> and <code>LinkedList</code>. The order of the LinkedList are as follows.

<ul>
<li>get(index) - O(n) </li>
<li>add(Object) - O(1) (provided a readymade last pointer is maintained in the linked list)</li>
<li>insertAt(int pos, Object value) - O(n) </li>
<li>remove(Object) - O(n)</li>
</ul>

blocks|key|3760967|text|我只想在bragBoy+Answer中添加一个更正：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3760968|对于LinkedList集合中的remove，最糟糕的复杂度应该是O(1)，因为它的内部使用了双向链表数据结构，这使得删除单个特定对象变得很容易。|offset|length|style|BOLD|3760969|entityMap^0|0|N|E|16|D|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@$D|L|E|M|F|G]|$D|N|E|O|F|G]]|9|@]|A|$]]|$1|H|3|-4|5|6|7|P|8|@]|9|@]|A|$]]]|I|$]]

I just want to add one correction in bragBoy Answer : 

The worst complexity for remove in LinkedList Collections should be O(1) as its internally uses the Doubly Linked List Data structure which makes easy to delete a single specific Object.

There are different collections are used in Java like hashtable, hashset, vector, treeset, treemap and hashmap. How are they implemented internally? What are the actual datastructure used for these collection? And, What is order?

It would be good if we discuss just a little bit about implementation of collection.

What is the actual datastructure used in implementation of collection and their order?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

Java中使用了不同的集合，如hashtable、hashset、vector、treeset、treemap和hashmap。它们是如何在内部实现的？这些集合使用的实际数据结构是什么？那么，什么是秩序呢？如果我们稍微讨论一下集合的实现，那就更好了。

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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