我们应该使用HashSet吗？

Question

HashSet是由HashMap支持的。根据它的JavaDoc：

该类实现了Set接口，由哈希表（实际上是一个HashMap实例）支持

当查看源代码时，我们还可以看到它们之间的关系：

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

因此，HashSet<E>由HashMap<E,Object>支持。对于我们应用程序中的所有HashSets，我们都有一个引用对象PRESENT，我们在HashMap中用作值。虽然存储PRESENT所需的内存可以忽略不计，但我们仍为地图中每个值存储对它的引用。

使用null代替PRESENT是否更有效呢？进一步考虑的问题是，如果情况允许使用Map而不是Set，我们是否应该完全放弃HashSet，直接使用HashMap。

触发这些想法的基本问题是我拥有具有以下属性的对象集合：

• 超过30,000个对象的大型集合
• 插入顺序无关紧要
• 高效检查是否包含某项
• 添加新项目到集合中无关紧要。在上述标准的背景下，选择的解决方案应该表现最佳，并尽量减少内存消耗。基于这个基础，数据结构HashSet和HashMap值得考虑。当思考替代方法时，关键问题是：

如何高效地检查包含？

我能想到的唯一答案是使用项哈希计算存储位置。我可能漏掉了什么。还有其他方法吗？

我看了各种问题，虽然它们让我对问题有了一些了解，但并没有完全回答我的问题：

• Java : HashSet vs. HashMap的区别
• 澄清Java实现HashSet/HashMap背后的事实
• Java中HashSet和HashMap的比较

我不想寻求任何替代库或框架建议来解决这个问题，但我想了解是否有其他方法来思考在Collection中高效地检查元素是否存在。

- hotzst

---

为什么要使用 null？据我所知，HashMap 中的 containsKey 检查 get 是否返回 null，因此这会破坏一些东西。 - Salem

1. 在HashMap中存储“null”可能会导致问题-它会破坏合同。
2. 我认为“null”引用需要与对任何其他对象的引用相同数量的内存，因此没有利润。

- dbf

问题的一部分就是这个：为什么不在HashMap中使用null作为值？ - hotzst

@hotzst null 和 PRESENT 需要相同的内存空间（都需要32位）。但是使用PRESENT，HashSet的实现更容易。例如，如果使用null，则HashSet.add()的实现将更加繁琐。 - ZhekaKozlov

Answer 1

简而言之，是的，您应该使用HashSet。它可能不是最高效的Set实现，但几乎从来没有关系，除非您处理大量数据。

在这种情况下，我建议使用专业库。如果可以使用枚举，则使用EnumMaps，如果您的数据大多是原语，请使用原始映射（如Trove），一堆其他针对特定数据类型进行优化的数据结构，甚至是内存中数据库。

别误会，我也喜欢性能调整，但只有在真正必要时才应替换内置数据结构。对于大多数情况，它们工作得非常好。

如果您确实想节省最后一点内存并且不介意插入，可以使用固定大小的数组，对其进行排序并每次进行二进制搜索。但我怀疑它比HashSet更有效。

- Silverclaw

---

你的回答引发了另一个问题：什么是null，对于Java已经有了答案。 - hotzst

Answer 2

哈希表和哈希集应该被完全不同地使用，因此也许两者不应该被比较哪个更有效率。哈希集将更适用于数学中的“集合”（例如{1,2,3,4}）。它们不包含重复项，并且只允许一个空值。而哈希图则更像是一个键值对系统。它们允许多个空值以及重复，但不允许重复的键值。我知道这可能回答了“哈希表和哈希集之间的区别”，但我认为我的观点是它们真的不能相互比较。

- Ash_s94

---

你正在回答什么问题？ - shmosel