Java 集合维护插入顺序
为什么某些集合数据结构不保持插入顺序？与维持插入顺序相比，有何特别之处？ 如果我们不维持秩序，我们能得到什么吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
表现。如果您想要原始插入顺序，可以使用
LinkedXXX类，它们按插入顺序维护一个附加链接列表。大多数时候你不在乎，所以你使用HashXXX，或者你想要一个自然顺序，所以你使用TreeXXX。在这两种情况下，为什么你应该支付链表的额外费用？Performance. If you want the original insertion order there are the
LinkedXXXclasses, which maintain an additional linked list in insertion order. Most of the time you don't care, so you use aHashXXX, or you want a natural order, so you useTreeXXX.In either of those cases why should you pay the extra cost of the linked list?集合不保持插入顺序。有些只是默认在末尾添加新值。仅当您按插入顺序确定对象的优先级或使用它以某种方式对对象进行排序时，维护插入顺序才有用。
至于为什么有些集合默认维护它而其他集合则不维护它，这主要是由实现引起的，有时只是集合定义的一部分。
列表维护插入顺序，因为在末尾或开头添加新条目是 add(Object ) 方法的最快实现。
集合 HashSet 和 TreeSet 实现不维护插入顺序，因为对对象进行排序是为了快速查找，并且维护插入顺序需要额外的内存。这会带来性能提升，因为插入顺序对于集合来说几乎从来不感兴趣。
ArrayDeque 双端队列可用于简单的队列和堆栈，因此您希望具有“先进先出”或“先进后出”行为，两者都要求 ArrayDeque 维护插入顺序。在这种情况下，插入顺序作为类契约的核心部分进行维护。
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.
Lists maintain insertion order as just adding a new entry at the end or the beginning is the fastest implementation of the add(Object ) method.
Sets The 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.
ArrayDeque a 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.
TreeSet/Map，使用它们的主要原因是自然迭代顺序以及SortedSet/Map接口中添加的其他功能。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.TreeSet/Map, the main reason to use them is the natural iteration order and other functionality added in theSortedSet/Mapinterface.取决于您需要实施什么才能做好。插入顺序通常并不有趣，因此无需维护它，以便您可以重新排列以获得更好的性能。
对于 Map，通常使用 HashMap 和 TreeMap。通过使用散列码，可以将条目放入易于搜索的小组中。TreeMap 维护插入条目的排序顺序，但代价是搜索速度较慢，但比 HashMap 更容易排序。
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.
当您使用 HashSet（或 HashMap）时，数据将根据对象的哈希存储在“存储桶”中。这样您的数据就更容易访问，因为您不必在整个集合中查找该特定数据，您只需在正确的存储桶中查找即可。
通过这种方式，您可以提高特定点的性能。
每个 Collection 实现都有其特殊性，以使其在特定条件下更好地使用。这些特性中的每一个都是有成本的。因此，如果您确实不需要它（例如插入顺序），您最好使用不提供它但更适合您的要求的实现。
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.
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.
为什么需要保持插入顺序呢？如果使用
HashMap，则可以通过key获取条目。这并不意味着它不提供执行您想要的操作的类。Why is it necessary to maintain the order of insertion? If you use
HashMap, you can get the entry bykey. It does not mean it does not provide classes that do what you want.O'Reilly Java Cookbook 中有一节名为“避免排序的冲动”，您应该问的问题实际上与您最初的问题相反......“我们通过排序获得了一些东西吗？”排序和维护该顺序需要付出很大的努力。当然排序很容易，但在大多数程序中通常无法扩展。如果您每秒要处理数千或数万个请求（insrt、del、get 等），无论您使用的是排序还是非排序数据结构都非常重要。
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.
好的......所以这些帖子与现在相比已经很旧了，但是根据您的需要或应用程序要求需要插入顺序，因此只需使用正确的集合类型即可。在大多数情况下，它是不需要的，但在您需要按照对象存储的顺序使用对象的情况下，我认为有明确的需要。我认为当你创建一个向导或一个流程引擎或类似的东西时，你需要从一个状态转到另一个状态或其他东西，顺序很重要。从这个意义上说，您可以从列表中读取内容，而无需让它跟踪您接下来需要的内容或遍历列表来查找您想要的内容。从这个意义上说，它确实有助于提高性能。这确实很重要，否则这些集合就没有多大意义。
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.
有些 Collection 不维护顺序，因为它们计算内容的 hashCode 并将其相应地存储在适当的存储桶中。
some Collection are not maintain the order because of, they calculate the hashCode of content and store it accordingly in the appropriate bucket.
我无法引用参考资料，但根据设计，
Collection接口的List和Set实现基本上是可扩展的Arrays.由于Collections默认提供在任意点动态添加和删除元素的方法，而Array则不提供这种方法。 t——插入顺序可能不会被保留。因此，由于有更多的内容操作方法，因此需要保留顺序的特殊实现。
另一点是性能，因为性能最好的集合可能不是保留其插入顺序的集合。然而，我不确定
Collections究竟如何管理其内容以提高性能。因此，简而言之，我能想到为什么存在保序
Collection实现的两个主要原因是：I can't cite a reference, but by design the
ListandSetimplementations of theCollectioninterface are basically extendableArrays. AsCollectionsby default offer methods to dynamically add and remove elements at any point -- whichArrays 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.
Another point is performance, as the most well performing
Collectionmight not be that, which preserves its insertion order. I'm however not sure, how exactlyCollectionsmanage their content for performance increases.So, in short, the two major reasons I can think of why there are order-preserving
Collectionimplementations are: