performance - 数据结构：hashmap vs linkedhashmap vs treemap

Question

我看到有很多关于这三者之间差异的问题。如果我错了，请告诉我，但如果我总结一下我能读到的内容：

• Hashmap：总体上会更有效率；O(1)（正常情况），O(N)（最坏情况，只有哈希算法不好）
• LinkedHashmap: 维护元素的插入顺序，比 hashmap 占用更多的内存
• Treemap：保持元素排序，O（log（n））（平衡时）

我的问题是：为什么我们需要维护插入顺序或元素排序，如果最后插入的性能，查找..更好hashmap？

Answer 1

我们有时需要主插入顺序，因为我们需要插入顺序来解决手头的问题。听起来有点重言式，但这确实是原因。一些数据是有序的，但也受益于随机访问。

同样用于排序。它提供了一种非常便宜地查找“下一个”或“上一个”项目的方法，同时对于任意查找仍然相当有效。一个示例是近似查找，例如，您知道要查找的条目以开头，Foo但您不知道其余的键是什么。

当您不需要任何这些操作时，Hashmap 的存在使事情变得更快更简单（没有顺序的概念），只需要精确查找。

Answer 2

我使用 Treemap 和 LinkedHashMap 是因为，虽然我可以自己对 HashMap 进行排序，但我怀疑我的解决方案是否会像 Java 的一样快或内存效率高。