有效处理 contains 操作的 Java 类

Question

我在迭代算法中使用 HashSet通过添加新对象(通过方法 add)，在每次算法迭代中动态扩大。我经常使用 contains 方法检查生成的对象是否已放入 HashSet 中。 观察到HashSet可能包含数千个对象。

以下是文档中有关 HashSet 类的引用:“假设哈希函数将元素正确地分散在存储桶中，此类将为基本操作(添加、删除、包含和大小)提供恒定的时间性能。”

除了文档中提供的其他注意事项(为简单起见未报告)之外，我发现 add 和 contains 是在恒定时间内执行的。请问，您能否建议 Java 中的另一种数据结构，为解决我的问题的“包含”操作提供更好的性能？

也接受来自 Apache Commons 或 Guava 的类。

Answer 1

只要您的对象具有正确实现的 hashCode() 方法，HashSet.contains() 的性能将尽可能好。这将确保存储桶之间的正确分配。

参见Best implementation for hashCode method