java - 我们应该使用 HashSet 吗？

Question

HashSet 由 HashMap 支持。来自它的 JavaDoc:

This class implements the Set interface, backed by a hash table (actually a HashMap instance)

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

// 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> 支持.对于我们应用程序中的所有 HashSet，我们有一个引用对象 PRESENT我们在 HashMap 中使用为值(value)。而存储所需的内存 PRESENT是可以忽略的，我们仍然为 map 中的每个值存储对它的引用。

使用null不是更高效吗？而不是 PRESENT ？那么进一步的考虑是我们是否应该放弃 HashSet完全直接使用HashMap , 鉴于情况允许使用 Map而不是 Set .

引发这些想法的基本问题是以下情况:我有一组具有以下属性的对象:

• 大量对象 > 30'000
• 插入顺序不相关
• 有效检查项目是否包含
• 向集合中添加新项目是不相关的 所选择的解决方案应该在上述标准的上下文中执行最佳，并最大限度地减少内存消耗。在此基础上的数据结构HashSet和 HashMap想到。在考虑替代方法时，关键问题是:

How to check containement efficiently?

我想到的唯一答案是使用项目哈希来计算存储位置。我可能在这里遗漏了一些东西。还有其他方法吗？

我查看了各种问题，确实对这个问题有所了解，但没有安静地回答我的问题:

• Java : HashSet vs. HashMap
• clarifying facts behind Java's implementation of HashSet/HashMap
• Java HashSet vs HashMap

我不是在寻找任何替代库或框架的建议来解决这个问题，但我想了解是否有其他方法可以考虑对 Collection 中的元素进行有效的包含检查。 .

Answer 1

简而言之，是的，您应该使用 HashSet。它可能不是最高效的 Set 实现，但这几乎无关紧要，除非您正在处理大量数据。

在这种情况下，我会建议使用专门的库。如果您可以使用枚举，则使用 E​​numMaps；如果您的数据主要是原始数据，则使用 Trove 之类的原始 map ；还有一堆针对特定数据类型优化的其他数据结构，甚至是内存数据库。

不要误会我的意思，我也是一个喜欢性能调优的人，但是只有在真正需要时才应该替换内置的数据结构。对于大多数情况，它们工作得很好。

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