维护插入顺序的 Java 集合

Java collections maintaining insertion order

提问by JavaUser

Why do some collection data structures not maintain the order of insertion? What is the special thing achieved compared to maintaining order of insertion? Do we gain something if we don't maintain the order?

为什么有些集合数据结构不维护插入顺序？与维护插入顺序相比，有什么特别之处？如果我们不维护秩序，我们会有所收获吗？

采纳答案by user207421

Performance. If you want the original insertion order there are the LinkedXXX classes, which maintain an additional linked list in insertion order. Most of the time you don't care, so you use a HashXXX, or you want a natural order, so you use TreeXXX. In either of those cases why should you pay the extra cost of the linked list?

表现。如果您想要原始插入顺序，则可以使用 LinkedXXX 类，它们按插入顺序维护一个额外的链表。大多数时候你并不关心，所以你使用一个HashXXX，或者你想要一个自然的顺序，所以你使用TreeXXX。在这两种情况下，为什么要支付链表的额外费用？

回答by Thorbj?rn Ravn Andersen

Depends on what you need the implementation to do well. Insertion order usually is not interesting so there is no need to maintain it so you can rearrange to get better performance.

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

For Maps it is usually HashMap and TreeMap that is used. By using hash codes, the entries can be put in small groups easy to search in. The TreeMap maintains a sorted order of the inserted entries at the cost of slower search, but easier to sort than a HashMap.

对于地图，通常使用 HashMap 和 TreeMap。通过使用散列码，条目可以放在易于搜索的小组中。TreeMap 以较慢的搜索为代价维护插入条目的排序顺序，但比 HashMap 更容易排序。

回答by Colin Hebert

When you use a HashSet (or a HashMap) data are stored in "buckets" based on the hash of your object. This way your data is easier to access because you don't have to look for this particular data in the whole Set, you just have to look in the right bucket.

当您使用 HashSet（或 HashMap）时，数据会根据对象的哈希值存储在“存储桶”中。通过这种方式，您的数据更易于访问，因为您不必在整个 Set 中查找此特定数据，只需在正确的存储桶中查找即可。

This way you can increase performances on specific points.

通过这种方式，您可以提高特定点的性能。

Each Collection implementation have its particularity to make it better to use in a certain condition. Each of those particularities have a cost. So if you don't really need it (for example the insertion order) you better use an implementation which doesn't offer it and fits better to your requirements.

每个 Collection 实现都有其特殊性，以使其在特定条件下更好地使用。这些特性中的每一个都有成本。所以如果你真的不需要它（例如插入顺序），你最好使用一个不提供它并且更适合你的要求的实现。

回答by FK82

I can't cite a reference, but by design the Listand Setimplementations of the Collectioninterface are basically extendable Arrays. As Collectionsby default offer methods to dynamically addand removeelements at any point -- which Arrays don't -- insertion order might not be preserved. Thus, as there are more methods for content manipulation, there is a need for special implementations that do preserve order.

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

Another point is performance, as the most well performing Collectionmight not be that, which preserves its insertion order. I'm however not sure, how exactly Collectionsmanage their content for performance increases.

另一点是性能，因为性能最好的Collection可能不是，它保留了插入顺序。但是，我不确定如何准确Collections管理他们的内容以提高性能。

So, in short, the two major reasons I can think of why there are order-preserving Collectionimplementations are:

所以，简而言之，我能想到为什么有保序Collection实现的两个主要原因是：

1. Class architecture
2. Performance

1. 类架构
2. 表现

回答by Michael Borgwardt

• The insertion order is inherently not maintained in hash tables- that's just how they work (read the linked-to article to understand the details). It's possible to add logic to maintain the insertion order (as in the LinkedHashMap), but that takes more code, and at runtime more memory and more time. The performance loss is usually not significant, but it can be.
• For TreeSet/Map, the main reason to use them is the natural iteration order and other functionality added in the SortedSet/Mapinterface.

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

回答by fastcodejava

Why is it necessary to maintain the order of insertion? If you use HashMap, you can get the entry by key. It does not mean it does not provide classes that do what you want.

为什么要保持插入顺序？如果使用HashMap，则可以通过 获取条目key。这并不意味着它不提供可以执行您想要的操作的类。

回答by josefx

The collections don't maintain order of insertion. Some just default to add a new value at the end. Maintaining order of insertion is only useful if you prioritize the objects by it or use it to sort objects in some way.

集合不维护插入顺序。有些只是默认在最后添加一个新值。维护插入顺序仅在您通过它优先考虑对象或使用它以某种方式对对象进行排序时才有用。

As for why some collections maintain it by default and others don't, this is mostly caused by the implementation and only sometimes part of the collections definition.

至于为什么有些集合默认维护而另一些不维护，这主要是由实现引起的，有时只是集合定义的一部分。

• Listsmaintain insertion order as just adding a new entry at the end or the beginning is the fastest implementation of the add(Object ) method.

• SetsThe HashSet and TreeSet implementations don't maintain insertion order as the objects are sorted for fast lookup and maintaining insertion order would require additional memory. This results in a performance gain since insertion order is almost never interesting for Sets.

• ArrayDequea deque can used for simple que and stack so you want to have ''first in first out'' or ''first in last out'' behaviour, both require that the ArrayDeque maintains insertion order. In this case the insertion order is maintained as a central part of the classes contract.

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

• SetsHashSet 和 TreeSet 实现不维护插入顺序，因为对象被排序以进行快速查找，并且维护插入顺序需要额外的内存。这会带来性能提升，因为插入顺序对于 Sets 来说几乎不感兴趣。

• ArrayDeque双端队列可用于简单的队列和堆栈，因此您希望具有“先进先出”或“先进后出”行为，两者都要求 ArrayDeque 保持插入顺序。在这种情况下，插入顺序作为类合同的中心部分进行维护。

回答by brown.2179

Theres's a section in the O'Reilly Java Cookbook called "Avoiding the urge to sort" The question you should be asking is actually the opposite of your original question ... "Do we gain something by sorting?" It take a lot of effort to sort and maintain that order. Sure sorting is easy but it usually doesn't scale in most programs. If you're going to be handling thousands or tens of thousands of requests (insrt,del,get,etc) per second whether not you're using a sorted or non sorted data structure is seriously going to matter.

O'Reilly Java Cookbook 中有一节叫做“避免排序的冲动” 你应该问的问题实际上与你最初的问题相反......“我们通过排序获得了什么吗？” 排序和维护该顺序需要付出很多努力。当然排序很容易，但在大多数程序中通常不会扩展。如果您要每秒处理数千或数万个请求（insrt、del、get 等），那么无论您使用的是排序还是非排序的数据结构，这都非常重要。

回答by Beaumont

Okay ... so these posts are old as compared to now, but insertion order is needed depending on your need or application requirements, so just use the right type of collection. For most part, it is not needed, but in a situation where you need to utilize objects in the order they were stored, I see a definite need. I think order matters when you are creating for instance a wizard or a flow engine or something of that nature where you need to go from state to state or something. In that sense you can read off stuff from the list without having it keep track of what you need next or traverse a list to find what you want. It does help with performance in that sense. It does matter or else these collections would not make much sense.

好的...所以这些帖子与现在相比是旧的，但是根据您的需要或应用程序要求需要插入顺序，所以只需使用正确类型的集合。在大多数情况下，它不是必需的，但在您需要按照对象存储的顺序使用对象的情况下，我看到了明确的需要。我认为，当您创建向导或流程引擎或需要从一个状态切换到另一个状态的那种性质时，顺序很重要。从这个意义上说，您可以从列表中读取内容，而无需跟踪您接下来需要什么或遍历列表以找到您想要的内容。从这个意义上说，它确实有助于提高性能。这确实很重要，否则这些集合将没有多大意义。

回答by Abhishek Singh

some Collection are not maintain the order because of, they calculate the hashCode of content and store it accordingly in the appropriate bucket.

一些 Collection 不维护顺序，因为它们计算内容的 hashCode 并将其相应地存储在适当的存储桶中。