Java中的小集:哪个数据结构？

Question

是否有任何好的参考,或者有人可以告诉我更多关于小集合上各种Java集合实现的性能(比如说1-100个元素)？O(1)vs O(log n)故事几乎与这些大小无关,但由于我需要处理数百万这些小集,因此性能确实很重要.我发现的大多数参考文献都没有提到太多.

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

• 初始化新集和/或硬拷贝旧集
• 添加/删除元素
• 迭代集合
• 计算hashCode()整个集合

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

• HashSet <T>:迭代似乎很糟糕(因此hashCode())
• TreeSet <T>:似乎有很高的开销
• LinkedHashSet <T>:根本没有这方面的经验,它有很高的开销吗？
• ArrayList <T>:本身速度快但不是一组,所以丑陋的技巧就像Collections.sort()需要的那样......

以上哪一项通常是首选的？或者我应该写自己的SmallSet<T>课程？

Answer 1

如果您确实追求性能，那么除了亲自测试之外，没有什么比这对您有帮助的了：

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

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

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

在您完成此类性能测试之前，我将给出我的标准建议：选择最佳可读选项，并且仅在使用可读性较差的选项有明显收益时才更改该选项。代码维护者（可能是未来的你）会为此感谢你。