Java: HashSet 和 HashMap 的区别

Question

我有一个处理海量数据的程序。最好将对象存储在实现哈希的容器中，因为程序会在容器中不断查找对象。

最初的想法是使用HashMap，因为该容器的get和remove方法更适合我需要的用途。

但是，我发现HashMap的内存消耗非常大，这是一个主要问题，所以我认为切换到HashSet会更好，因为它每个元素只使用而不是，但是当我查看其实现时，我了解到它使用底层的HashMap！这意味着它不会节省任何内存！

所以这是我的问题：

• 我的所有假设都正确吗？
• HashMap是否浪费内存？更具体地说，每个条目的开销是多少？
• HashSet是否像HashMap一样浪费内存？
• 还有其他基于哈希的容器可以显著减少内存消耗吗？

正如评论中要求的那样，我将对我的程序进行一些扩展：hashMap旨在容纳另外两个对象的一对对象和一些数值（float）从它们计算而来。在此过程中，它提取其中一些并输入新的对。给定一对对象，它需要确保它不持有此对或删除它。可以使用float值或对偶对象的hashCode进行映射。

此外，当我说“海量数据集”时，我指的是大约4 * 10 ^ 9个对象。

- Ravid Goldenberg

---

@JBNizet 我还没有测试过HashSet，因为已经编写并在较小的数据集上运行了使用HashMap的代码，所以在将其修改为HashSet之前，考虑一下这是否有帮助是不是更合理？ - Ravid Goldenberg

那么，您已经测量并证明在您的用例中使用 HashMap 确实消耗了过多的内存吗？这个用例是什么？ - JB Nizet

你首先说你正在使用HashMap而不是HashSet，尽管它们是完全不同的集合类型。我们所知道的关于你的用例（即你的应用程序必须执行的操作）是它必须处理“巨大的数据集”。由于信息太少，我们无法推荐任何解决方案。此外，我看到了很多关于“巨大”数据集的问题，其中“巨大”实际上意味着“大约1000”，这实际上是微不足道的，因此我更喜欢询问。 - JB Nizet

@petric，我编辑了我的答案，虽然它没有回答你所有的问题，但包含了一些可能有用的提示。 - void

@petric，非常欢迎您。 - void

Answer 1

在这个网站上有关于Java集合性能的非常有用的提示。

HashSet基于HashMap<T, Object>构建，其中值是单例的“present”对象。这意味着HashSet的内存消耗与HashMap相同：为了存储SIZE个值，您需要32 * SIZE + 4 * CAPACITY字节（加上您的值的大小）。这绝对不是一个内存友好型的集合。

THashSet可能是HashSet最简单的替代集合 - 它实现了Set和Iterable，这意味着您只需在初始化set时更新一个字母即可。

THashSet使用单个对象数组来存储其值，因此它使用4 * CAPACITY字节进行存储。正如您所看到的，与JDK HashSet相比，在相同的负载因子下，您将节省32 * SIZE字节，这是一个巨大的改进。

另外，我从这里拿到了下面的图片，可以帮助我们记住选择正确的集合。

- void

Answer 2

我的所有假设都是正确的吗？

您是正确的，HashSet 是使用 HashMap 实现的，因此使用 HashSet 不会节省任何内存。

如果您正在创建大量元素的映射，应该根据您的最佳知识构造 HashMap 并设置 initialCapacity，以防止重复重新散列（从而导致内存抖动）。

HashMap 内存浪费吗？更具体地说，每个条目的开销是多少？

不，这并不浪费。开销是一个基础数组（大小由loadFactor修改），以及每个键值对的Entry对象。除了存储键和值之外，entry对象还在槽中存储指向下一个条目的指针（如果两个或更多条目占用基础数组中的同一槽）。默认的0.75负载因子将基础数组大小保持在条目数量的133％。

非常具体地说，每个条目的内存开销包括：

• entry对象引用键，
• entry对象引用值，
• entry对象引用下一个条目，
• 以及基础数组引用条目（除以负载因子）。

对于基于哈希的集合来说，很难比这更加精简。

HashSet是否与HashMap一样浪费？

使用HashSet而不是HashMap不会提高内存效率。

是否有其他基于哈希的容器可以显著减少内存消耗？

如果您的键是原始类型（例如int），则存在自定义的Map和Set实现（在第三方库中），这些实现使用更节省内存的数据结构。

- gknicker

---

谢谢您的回答。当我使用“浪费”的词时，我并不是指“不恰当地执行任务”，而是指选择使用它们会消耗大量内存，因为使用了许多引用，每个项目有2个引用，除了实际对象和键的大小之外，我是对的吗？ - Ravid Goldenberg

不用谢。我知道你的意思。我已经更新了我的答案，更具体地说明了开销。 - gknicker

Answer 3

HashSet和HashMap使用的内存一样多是真的。两者之间的区别在于HasSet实现了Set，即它不关心与键相关联的任何值，只关心特定值的存在或缺失。HashMap则关注存储/检索（put/get）每个键对应的值。虽然HashMap/HashSet将数据存储在通常比元素数量略大的数组中，但这不应该是太大的问题，因为负载因子为0.75。这意味着当元素数量达到底层数组大小的75％时，HashMap将增长。比大型映射更令人担忧的是许多空映射，因为HashMap的默认大小为16。这可以通过将初始容量设置为0来抵消。您还可以使用TreeMap，但由于TreeMap基于引用而不是数组，因此您可能会浪费更多空间，尤其是在处理较大的映射时，同时也会失去一些速度。 TreeMap的主要好处是它以有序状态维护键，因此如果需要排序，则可以使用该方法。

此外，当您不能或不想为键类型自定义实现equals和hashCode方法时，可以使用TreeMap进行编程。相反，您可以为键类型创建一个比较器。例如，要基于不区分大小写的字符串创建地图/集，请将String.CASE_INSENSITIVE_ORDER用作TreeSet的比较器。

- Joseph K. Strauss