5

有没有办法通过指定项目的顺序来优化 java.util.Collection 中的插入速度？

例如

java.util.Set<String> set = java.util.TreeSet<String>();

将这个解决方案：

set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("E");

比这个更快（随机顺序）？

set.add("E");
set.add("D");
set.add("C");
set.add("A");
set.add("B");

（以及其他集合的相同问题：HashMap，hastable ...）

谢谢

4

5 回答 5

8

简单的答案是“时间看看”。

另一个答案是“没关系”。这似乎是一个微优化，几乎不值得付出努力。我认为它属于“微优化剧院的悲惨悲剧”的范畴。

于 2009-02-22T18:11:33.520 回答
6

java.util.Map 和 java.util.Set 不行，因为它们是接口，有不同的实现。

对于具体的实现，这不是值得的优化。如果您在性能方面遇到问题，请选择更合适的实现，或者重新考虑您需要存储什么以及如何存储。

在一台普通的笔记本电脑上，将 5000 个随机数插入 HashSet 大约需要一毫秒，那么您要插入多少百万个元素才能使这种优化变得有价值？

于 2009-02-22T18:15:37.440 回答
3

红黑树（用于实现 Java 的TreeSet/TreeMap ）的插入时间保证最坏情况为 O(log n)。如果项目按特定顺序排列可能会更快，但我不确定那会是什么（可能预排序最快？）。

插入哈希表是 O(1)（恒定时间）操作。插入的主要工作是计算hashcode。

编辑：Starblue 建议预排序可能会产生最差的性能，因此您可以尝试随机排序。

于 2009-02-22T18:11:16.437 回答
2

基于散列的集合和基于树的集合之间自然存在巨大差异。

基于树的对象受益于插入的元素排序（例如，字符串之间的比较），因此当您有可比较的对象（如字符串）时，最好使用它们。TreeSet/TreeMap/等。在标准集合中应该是平衡的（红黑树），所以插入顺序并不重要。如果它不平衡，那么插入顺序就会很重要，因为您最终可能会得到一个链而不是树。

在哈希表中，加载因子和哈希函数决定了一切，但如果您正在处理字符串，您可能甚至不打扰哈希会更好。

如果您需要一组字符串来处理许多重叠的字符串，Trie 可能会更节省内存，但我认为库中没有。

于 2009-02-22T18:14:03.157 回答
1

在采取优化措施时要小心考虑数据结构的特征。举一个极端的例子，将元素按排序顺序插入二叉树会产生一个链表。

于 2009-02-22T18:53:14.310 回答