代码之家 › 专栏 › 技术社区 › Niklas Mertsch

Java集合:这个非常特殊的情况下要使用什么集合?

hashset collections java

Niklas Mertsch · 技术社区 · 6 年前

我有以下场景,正在寻找“最佳”实现:

我想在 java.util.Collection 实现接口
所有项目都保证有一个独特的 hashCode
我知道最大值 n 要存储的项(最大 capacity 初始化时已知)
这个 哈希码 是介于 0 到 n
秩序不重要,不需要复制品( Set -需要属性)
项目可以添加,但永远不会删除
履行 contains 非常重要(期望: O(1) 至少 O(log_n) )

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

我的第二个想法是使用本机数组( new item[n] )使用 哈希码 作为索引。这似乎是具有最佳性能的实现,但我的接口期望 java.util.collection集合 收藏将与 包含 和 add ,这与第二种方法的好处不兼容。

是我遗漏了什么,还是我必须接受 HashSet 为了得到最好的表现?

2 回复 | 直到 6 年前

Eran 6 年前

使用 HashSet 仍然会给您带来良好的性能,但是考虑到您描述的特定需求(并且假设 n 它不太大),您可以创建自己的“ARAYSET”实现 Set 接口:

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

这个解决方案可能比 哈希表 ,因为它包含较少的开销。然而,在内存使用方面,它将是扩展的。 n 是大的。

Naim 6 年前

考虑到这个要求,我建议您使用hashset。它会表现得更好。正如您所提到的,元素的最大数量和集合的最大容量都是相同的大小。此外,每个元素都有一个唯一的hashcode。在这种情况下,散列键冲突很少发生变化。所以不要担心contains函数。使用上述数据集包含将在O(1)中执行。同样地添加也将按固定顺序执行。即O(1)。

推荐文章

Mark Roworth · 未知类型IEnumerable上的C#泛型foreach

2 年前

Giffyguy · 如何限制在构造向量后调用'resize()'?

2 年前

vytaute · 返回表类型时Oracle函数中的类型错误

2 年前

bbgghh · 在scala中连接两个列表时如何处理不匹配的键

2 年前

dev-chicco · Laravel系列寻找常见物品

2 年前

Mitch · Laravel-雄辩的单品合并系列

6 年前

maheryhaja · 将Java8 IntStream收集到Deque接口中

6 年前

Kieran · 为什么类X可以从集合继承<X>

6 年前

John · 如何在不返回集合本身的情况下返回集合的数据?

6 年前

Niklas Mertsch · 在泛型集合中实现移除(对象o)

6 年前