java - Java 中的小集合 : which datastructure?

Question

是否有关于小型 集合(例如 1-100 个元素)的各种 Java 集合实现的性能的任何好的引用，或者有人可以告诉我更多相关信息吗？ O(1) vs O(log n) 的故事与这些大小几乎无关，但由于我需要处理数百万个这样的小集合，性能当然很重要。我发现的大多数引用文献都没有过多提及这一点。

我需要对这些集合执行以下操作(通常每组只需执行几次):

• 初始化一套新的和/或硬拷贝一套旧的
• 添加/删除元素
• 遍历集合
• 计算hashCode()整组的

我认为这些是比较可行的选项(假设比较/散列 T 几乎是免费的):

• HashSet :似乎不擅长迭代(因此在 hashCode() )
• TreeSet :开销似乎高得离谱
• LinkedHashSet :完全没有这方面的经验，开销大吗？
• ArrayList :本身很快但不是一个集合，像Collections.sort()这样丑陋的技巧需要...

通常首选以上哪项？或者我应该自己写 SmallSet<T>类(class)？

Answer 1

如果你真的在寻找性能，那么没有什么比自己测试更能帮助你的了:

• 您是否不断地为它们分配新的资源？如果是这样，垃圾收集可能比其他情况更有意义
• 您是否只分配了一次并需要快速访问？哈希碰撞将对此产生影响
• 您是否经常更改它们？

您需要设置一个与您的实际使用类似的测试用例 - 测试足够长的时间以便 GC 启动，然后您会看到效果。

如果您检测到它们之间的关键差异，请在每次更新 JVM 后重新运行测试，因为实现可能会发生变化。

在您完成此类性能测试之前，我将给出我的标准建议:选择可读性最好的选项，并且只有在使用较差的可读性有明显好处时才更改它。代码维护者(可能是 future 的你)会为此感谢你。