优化java.util.Map/Set中的插入速度

Question

有没有办法通过指定项目的顺序来优化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 ......)

谢谢

Answer 1

简单的答案是"时间和看到".

另一个答案是"无所谓".这似乎是微观优化,几乎不值得努力.我认为它属于"微优化剧场悲剧悲剧"的范畴.

@Pierre对BDB的插入实际上会产生巨大的影响:至少对于本机BDB,按键顺序插入比随机插入快一些(是的,我们测试了这个).事实上,我们的处理是通过写入磁盘完成的,合并排序,插入和组合比直接插入快5倍.但是,由于多种原因(例如,它不是瓶颈,bdb将是;(b)可能没有任何优化),尝试优化散列/树映射的可能性更小. (2认同)

Answer 2

对于java.util.Map和java.util.Set没有,因为这些是接口,并且有不同的实现.

对于具体实现,它不是一个值得优化的.如果您遇到性能问题,请选择更合适的实施方案,或重新考虑您需要存储的内容和方式.

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

Answer 3

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

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

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