Java集合维护插入顺序

Question

为什么有些数据结构不保留插入顺序？与保留插入顺序相比，它们所实现的特殊功能是什么？如果我们不保留顺序，是否会获得一些优势？

- JavaUser

---

дҫӢеҰӮпјҢдёәд»Җд№Ҳjava.util.HashSetйңҖиҰҒз»ҙжҠӨжҸ’е…ҘйЎәеәҸпјҹ - 卢声远 Shengyuan Lu

在维护顺序的同时，我们是否会失去任何东西？相反，如果我们不维护顺序，我们是否会获得一些东西？ - JavaUser

想想看，将元素附加/前置到链表中比在中间插入更容易吧？ - st0le

Answer 1

性能。如果您想要原始插入顺序，则有维护额外链接列表的LinkedXXX类。大多数时候您不关心，所以使用HashXXX，或者您想要自然顺序，所以使用TreeXXX。在这两种情况下，为什么要支付额外的链表成本呢？

- user207421

---

ArrayList在答案中的位置是什么？ - ADTC

@ADTC 这不适合作为答案。 - user207421

ArrayList 保持插入顺序，其底层是数组，但我认为性能比 LinkedXXX 类要差？ - ADTC

@ADTC 如果您未使用索引插入方法或对其进行排序，则它将保持插入顺序，LinkedList 也是如此。’使用数组作为支撑‘是不相关的。两种情况下的性能都在Javadoc中有描述。 - user207421

Answer 2

这些集合不维护插入顺序。有些集合只是默认在末尾添加新值。仅当您通过它来对对象进行排序或以某种方式对其进行优先级排序时，保持插入顺序才有用。

至于为什么一些集合默认维护插入顺序，而其他的则不维护，这主要是由实现原因造成的，有时也是集合定义的一部分。

• Lists（列表）保持插入顺序，因为在末尾或开头添加一个新条目是add(Object )方法最快的实现方式。

• Sets（集合） HashSet和TreeSet实现不保持插入顺序，因为对象已经排序以实现快速查找，保持插入顺序需要额外的内存。这会导致性能提升，因为对于Sets，插入顺序几乎从不重要。

• ArrayDeque 一个双端队列可用于简单的队列和栈，所以您希望具有“先进先出”或“后进先出”的行为，两者都需要ArrayDeque维护插入顺序。在这种情况下，插入顺序是类约定的核心部分。

- josefx

Answer 3

• 在哈希表中，插入顺序本质上是不被维护的 - 这就是它们的工作原理（请阅读链接文章以了解详情）。可以添加逻辑来维护插入顺序（如LinkedHashMap），但这需要更多的代码，在运行时需要更多的内存和时间。性能损失通常不显著，但也可能存在。
• 对于TreeSet/Map，主要使用它们的原因是自然迭代顺序和其他在SortedSet/Map接口中添加的功能。

- Michael Borgwardt

---

仅作为一个快速的侧记：严格来说，Map 实现不是 Collection，因为它们没有实现 Collection 接口。它们具有类似的方法，但仅此而已。请参阅：http://download.oracle.com/javase/1.4.2/docs/guide/collections/overview.html (#Collection Interfaces) 尽管如此，OP 的问题很可能也涉及到了映射。 - FK82

Answer 4

取决于您需要实现什么功能。插入顺序通常不重要，因此无需维护它，可以重新排列以获得更好的性能。

对于 Map，通常使用 HashMap 和 TreeMap。通过使用哈希码，条目可以放置在易于搜索的小组中。TreeMap 以已插入条目的排序顺序为代价维护一个排序顺序，但比 HashMap 更容易排序，但搜索速度较慢。

- Thorbjørn Ravn Andersen

Answer 5

当你使用HashSet（或HashMap）时，数据根据对象的哈希值被存储在“桶”内。这样，你可以更容易地访问数据，因为你不需要在整个集合中查找特定的数据，只需在正确的桶中查找即可。

这样，你可以提高特定点上的性能。

每个集合实现都有其独特之处，使其更适用于某些条件下的使用。每个特殊之处都有一个代价。因此，如果你不是非常需要它（例如插入顺序），最好使用不提供它并更适合你的要求的实现。

- Colin Hebert

Answer 6

为什么需要保持插入顺序？如果使用HashMap，您可以通过键获取条目。这并不意味着它不提供符合您要求的类。

- fastcodejava

Answer 7

在O'Reilly Java Cookbook中有一个名为“避免排序冲动”的章节。你应该问的问题实际上与你最初的问题相反...“通过排序我们能获得什么？”排序和维护顺序需要很大的努力。当然，排序很容易，但在大多数程序中通常不会扩展。如果你要处理成千上万个请求（插入、删除、获取等）每秒，无论你使用排序还是非排序数据结构都会严重影响。

- brown.2179

Answer 8

由于一些集合计算内容的哈希码并相应地存储到适当的桶中，因此这些集合不维护顺序。

- Abhishek Singh

Answer 9

好的...这些帖子相对于现在来说有点老了，但插入顺序取决于您的需求或应用程序要求，因此只需使用正确类型的集合即可。在大多数情况下，它是不需要的，但在需要按存储顺序利用对象的情况下，我认为绝对需要。我认为当您创建向导或流程引擎等需要从状态到状态转换的东西时，顺序很重要。在这种意义上，您可以从列表中读取内容，而无需跟踪下一个所需内容或遍历列表以查找所需内容。在这种意义上，它确实有助于性能。它确实很重要，否则这些集合就没有太多意义。

- Beaumont

Answer 10

我无法引用参考文献，但是按设计来说，Collection 接口的 List 和 Set 实现基本上是可扩展的 Array。由于 Collections 默认提供在任何时候动态“添加”和“删除”元素的方法，而 Array 不提供这些方法，因此插入顺序可能不会被保留。 因此，由于有更多的内容操作方法，需要特殊的实现来保留顺序。

另一个问题是性能，最好的执行效果的 Collection 可能并不是保留其插入顺序的集合。然而，我不确定 Collections 如何管理其内容以提高性能。

因此，简而言之，我认为存在保持顺序的 Collection 实现的两个主要原因是：

1. 类架构
2. 性能

- FK82

---

请注意，Arrays是一个实际的类，而数组是一种特殊类型的容器对象。我也非常确定LinkedList实际上确实使用了链表，但我还没有阅读过代码。 :-) - wds

澄清一下：据我所知，LinkedList 是一个 List（可扩展的 Array），其插入顺序在另一个 List 中得以维护（这两个 List 是链接的，因此得名）。或者，我对此有误吗？ - FK82

一篇非常混乱和令人困惑的帖子。LinkedList不是可扩展数组，List也不是：这取决于实现方式。它们都不包含“另一个List”。我不知道你所说的“哪些数组不包含”。你的第二段基本上没有意义。你的结论并不符合你的前提。 - user207421

另外，Array 对象没有提供动态删除和添加元素的方法。这就是为什么首先存在 List 的原因。我的第二段说的是你在帖子中所说的内容。别在第一印象上发火，伙计。 - FK82

因此，'So'引出了你的结论。你没有问问题。没有'Array object'。有一个ArrayList类，它确实提供了这些方法。我的其他陈述仍然是正确的。 - user207421