47

查看 Java 6 的源代码，HashSet<E>实际上是使用 实现HashMap<E,Object>的，在 Set 的每个条目上使用虚拟对象实例。

我认为条目本身的大小浪费了 4 个字节（在 32 位机器上）。

但是，为什么还在使用呢？除了更容易维护代码之外，还有什么理由使用它？

4

7 回答 7

22

其实，不只是HashSet。 Java 6 中接口的所有实现Set都基于底层的Map. 这不是要求；这就是实现的方式。您可以通过查看Set.

你的主要问题是

但是，为什么还在使用呢？除了更容易维护代码之外，还有什么理由使用它？

我认为代码维护是一个很大的激励因素。防止重复和膨胀也是如此。

Set并且Map是类似的接口，因为不允许重复的元素。（我认为唯一Set 不受a 支持的Map是CopyOnWriteArraySet，这是一个不寻常的集合，因为它是不可变的。）

具体来说：

从以下文档Set：

不包含重复元素的集合。更正式地说，集合不包含一对元素 e1 和 e2 使得 e1.equals(e2)，并且最多包含一个空元素。正如它的名字所暗示的，这个接口模拟了数学集合抽象。

除了从 Collection 接口继承的那些之外，Set 接口对所有构造函数的合约以及 add、equals 和 hashCode 方法的合约进行了额外的规定。为方便起见，此处还包括其他继承方法的声明。（这些声明随附的规范已针对 Set 接口进行了定制，但它们不包含任何附加规定。）

毫不奇怪，对构造函数的附加规定是，所有构造函数都必须创建一个不包含重复元素的集合（如上所述）。

从Map：

将键映射到值的对象。地图不能包含重复的键；每个键最多可以映射到一个值。

如果您可以Set使用现有代码实现您的 s，那么您可以从现有代码中实现的任何好处（例如速度）也会对您产生影响Set。

如果您选择在Set没有Map支持的情况下实现 a，则必须复制旨在防止重复元素的代码。啊，可口的讽刺。

也就是说，没有什么能阻止你Set以不同的方式实现你的 s 。

于 2010-02-10T10:04:41.723 回答
5

我的猜测是 HashSet 最初是根据 HashMap 实现的，以便快速轻松地完成它。就代码行数而言，HashSet 是 HashMap 的一小部分。

我猜它仍然没有被优化的原因是害怕改变。

然而，浪费比你想象的要糟糕得多。在 32 位和 64 位上，HashSet 比需要大 4 倍，而 HashMap 比需要大 2 倍。HashMap 可以用一个包含键和值的数组来实现（加上冲突链）。这意味着每个条目有两个指针，或 64 位 VM 上的 16 个字节。实际上，HashMap 每个条目都包含一个 Entry 对象，它为指向 Entry 的指针添加了 8 个字节，为 Entry 对象头添加了 8 个字节。HashSet 每个元素也使用 32 个字节，但浪费是 4x 而不是 2x，因为它每个元素只需要 8 个字节。

于 2011-05-07T16:48:37.820 回答
4

我猜它从来没有成为实际应用程序或重要基准测试的重大问题。为什么要使代码复杂化却没有真正的好处？

另请注意，在许多 JVM 实现中，对象大小被四舍五入，因此实际上可能不会增加大小（我不知道这个例子）。此外，代码HashMap很可能会被编译并在缓存中。在其他条件相同的情况下，更多代码 => 更多缓存未命中 => 性能降低。

于 2010-02-10T09:49:04.313 回答
3

是的，你是对的，少量的浪费是确定的。小，因为对于每个条目，它都使用相同的对象PRESENT（声明为 final）。因此，唯一的浪费是 HashMap 中每个条目的值。

大多数情况下，我认为，他们采用这种方法是为了可维护性和可重用性。（JCF 开发者会想，反正我们已经测试过 HashMap，为什么不重用它。）

但是，如果您拥有大量收藏，并且您是个记忆狂，那么您可能会选择更好的替代品，例如Trove或Google Collections。

于 2010-02-10T09:50:22.080 回答
3

我看了你的问题，想了想你说了什么。所以这是我对实施的看法HashSet。

有必要让虚拟实例知道该值是否存在于集合中。

看一下add方法

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

Abd 现在让我们看一下 put 返回值

@return 返回与 key 关联的先前值，如果没有 key 映射，则返回 null。（返回 null 还可以指示映射先前将 null 与 key 关联。）

所以PRESENT对象只是用来表示集合中包含 e 值。我想你问为什么不使用null而不是PRESENT. 但是，您将无法区分该条目是否以前在地图上，因为它map.put(key,value)总是会返回null并且您无法知道该键是否存在。

话虽如此，您可能会争辩说他们本可以使用这样的实现

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

我猜他们浪费了 4 个字节来避免计算两次密钥的 hashCode，因为它可能很昂贵（如果要添加密钥）。

如果您质疑他们为什么使用会HashMap浪费 8 个字节的 a（因为Map.Entry

于 2010-02-10T10:03:12.973 回答
0

在搜索了这样的页面后，想知道为什么标准实现效率有点低，发现 com.carrotsearch.hppc.IntOpenHashSet

于 2013-09-18T19:44:31.357 回答
-3

您的问题：我认为条目本身的大小浪费了 4 个字节（在 32 位机器上）。

只需为 hashset 的整个数据结构创建一个 Object 变量，这样做可以避免重新编写整个 hashMap 类型的代码。

private static final Object PRESENT = new Object();

所有的键都有一个值，即 PRESENT 对象。

于 2012-11-19T21:42:48.740 回答