Java集合实现（例如HashMaps vs HashSet vs HashTable ...），选择错误的代价是什么？

Question

在我的代码中，我默认使用ArrayList作为所有列表的实现，HashMap作为所有映射的实现，HashSet作为所有集合的实现。

从实际角度来看，如果选择错误的实现，会失去多少灵活性、可伸缩性、可读性和性能？什么时候值得花时间决定使用哪种实现？

在某些情况下，我肯定会清楚地看到为什么有人会使用LinkedList而不是ArrayList。什么时候有人觉得必须使用HashMap而不是TreeMap或HashTable？那Set呢？

问题：

1. 选择不当的代价是什么？
2. 有人有选择错误实现并导致数据中心着火的灾难故事吗？
3. 有什么好的经验法则吗？
4. 有哪些你不能没有的晦涩的集合实现？

我已阅读：

• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/TreeMap.html：TreeMap是一个基于红黑树实现的有序映射表，可以按照键的自然顺序或者指定顺序进行排序。
• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/HashMap.html：HashMap是一个基于哈希表实现的无序映射表，可以快速查找键值对。
• Java: ArrayList for List, HashMap for Map, and HashSet for Set? 等等...

我认为this问题从理论上来看很相关，但我更感兴趣的是现实世界中的答案。

- Ethan Heilman

---

这实际上像是四个问题，更像是一次讨论而不是一个问题。 - cletus

可能相关的答案：http://bit.ly/1NSlx - OscarRyz

哪种数据结构使用更多内存？ - Ethan Heilman

问题 - 用于请求信息的语言表达？这怎么不符合问题的定义呢？ - Ethan Heilman

[rules-of-thumb]是一个元标签，这里不需要添加它。 - Bhargav Rao

Answer 1

这是一个非常普遍的问题，但我会提供一些想法。

如果您的编程面向接口，则灵活性不会受到很大影响。例如：

void foo(List<E> list);

选择不当的代价可能在性能惩罚中体现。例如，如果你需要直接访问（如ArrayList），而选择了LinkedList，则会导致性能下降。

集合也存在类似的问题。如果您希望保持无重复项的排序集合，则使用SortedSet比HashSet更明智。在后者中，您需要手动对整个集合进行排序（即调用Collections.sort()）。

<EDIT>

关于maps，有很多不同的实现。每个实现都有不同的目的。 例如，有SortedMap，类似于SortedSet。然后，还有WeakHashMap，它不像HashMap那样工作，因为键可以被垃圾回收器删除。 正如你所想象的那样，HashMap和WeakHashMap之间的选择并不是微不足道的。总是取决于你想要用它们实现什么。 </EDIT> 关于这个故事，在我的当前项目中，我们用SortedSet替换了HashSet，因为性能受到了影响。然而数据中心并没有着火。 这是我的一些见解。

- Tom

Answer 2

只要你遵循良好的面向对象编程实践，依赖于抽象类型，那还有什么关系呢？

例如，如果你发现使用了错误的Map，只需更改正在使用的实现，因为所有依赖项都在Map上，所以一切都像以前一样工作，只是性能特征不同而已。

- Nick Holt

---

如果你依赖于ArrayList的某些性能特征，但意识到需要使用LinkedList，那么可能会出现问题。你可能需要重写代码中效率低下的部分，改为使用LinkedList。 - Ethan Heilman

Answer 3

我认为你可以放心地使用HashMap、HashSet和ArrayList作为你的主要实现。当你需要一个排序集时，知道TreeSet是可用的很好；同样，当你做递归类型的事情时，有LinkedList在你的后备口袋里也很不错。但是按照接口编程，然后你可以根据需要交换实现。如果同一集合需要作为（例如）LinkedList和ArrayList进行处理，从一个构造另一个也没有什么大不了的。

使用你列出的默认实现进行工作。当存在性能问题，并且有理由相信替代实现会更好时，请将其替换并测量差异。当你需要特殊行为（例如排序集）时，请使用特殊类。

这种方法到目前为止还没有让我失望过。

- Carl Manaster