为什么Sun Java中的HashSet实现使用HashMap作为其后盾？

Question

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

我认为这对于条目本身的大小来说浪费了4个字节(在32位机器上).

但是,为什么它仍在使用？是否有任何理由使用它,除了使代码更容易维护？

Answer 1

实际上,它不仅仅是HashSet. Java 6中的所有Set接口实现都基于底层Map.这不是必要条件; 这就是实施的方式.您可以通过查看各种实现的文档来亲眼看到Set.

你的主要问题是

但是,为什么它仍在使用？是否有任何理由使用它,除了使代码更容易维护？

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

Set并且Map是类似的接口,因为不允许重复的元素.(我认为唯一Set 不支持的Map是CopyOnWriteArraySet,这是一个不寻常的集合,因为它是不可变的.)

特别:

来自以下文件Set:

不包含重复元素的集合.更正式地说,集合不包含元素对e1和e2,使得e1.equals(e2)和至多一个null元素.正如其名称所暗示的,该界面模拟数学集抽象.

除了从Collection接口继承的那些之外,Set接口在所有构造函数的契约以及add,equals和hashCode方法的契约上放置了其他规定.为方便起见,此处还包含其他继承方法的声明.(这些声明附带的规范是针对Set接口定制的,但它们不包含任何其他规定.)

对构造函数的额外规定,毫不奇怪,所有构造函数必须创建一个不包含重复元素的集合(如上所定义).

来自Map:

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

如果您可以Set使用现有代码实现自己的代码,那么您可以从现有代码中获得的任何好处(例如速度)也会累积到您的代码中Set.

如果您选择在Set没有Map支持的情况下实现,则必须复制旨在防止重复元素的代码.啊,好吃的讽刺.

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

Answer 2

我的猜测是 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 个字节。