Java 集合 : What collection to use is this very specific case?

Question

我有以下情况并且正在寻找“最佳”实现:

1. 我想将项目存储在 java.util.Collection 中实现一个接口(interface)
2. 保证所有项目都具有唯一的 hashCode
3. 我知道最大数量n要存储的项目数(最大值 capacity 在初始化时已知)
4. hashCode介于 0 之间至 n
5. 顺序不重要，不需要重复(需要 Set - 属性)
6. 可以添加项目，但永远不会删除
7. contains 的表现非常重要(要求:O(1)，至少O(log_n))

我的第一个想法是使用 new HashSet<item>(n+1, 1.0) , 但经过一番阅读后，我发现它对 hashCode 应用了一个内部哈希函数的项目，所以散列冲突仍然会发生，即使 hashCodes是独一无二的 hachCode <= n .

我的第二个想法是使用原生数组 ( new item[n] ) 并使用 hashCode作为索引。这似乎是性能最好的实现，但我的界面需要一个 java.util.Collection该系列将与 contains 一起使用和 add ，这与第二种方法的好处不兼容。

我是不是遗漏了什么，还是我必须接受 HashSet 的开销和冲突？以获得最佳性能？

Answer 1

使用 HashSet 仍然会给你很好的性能，但是考虑到你描述的具体要求(并假设 n 它不是太大)，你可以创建你自己的“ArraySet "Set 接口(interface)的实现:

• 它将有一个长度为 n+1 的后备数组来存储数据。
• contains 将使用元素的 hashCode 来查找匹配 hashCode() 的索引是否具有非空值。<
• add 将使用所添加元素的 hashsCode 来查找您应将元素添加到的数组的索引。
• 任何其他必需的方法将以类似方式实现。

此解决方案可能比 HashSet 稍微高效一些，因为它包含的开销更少。但是，如果 n 很大，它会在内存使用方面膨胀。