为什么Sun Java中的HASSET实现使用HASMAP作为后盾?

事实上,这不仅仅是 HashSet . 所有 的实现 Set Java 6中的接口是基于底层的 Map . 这不是一个需求,而是实现的方式。您可以通过查看文档了解 Set .

你的主要问题是

但是,为什么还要用呢?有 有什么理由用它除了做它 更容易维护代码?

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

集合 和 地图 是相似的接口,因为不允许重复的元素。(我认为只有 设置 不 由A支持 地图 是 CopyOnWriteArraySet ,这是一个不寻常的集合,因为它是不可变的。)

明确地:

从 documentation of Set :

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

设置接口添加了 规定,继承的除外 从集合接口,在 所有施工人员的合同 附加合同等于和 哈希代码方法。声明 其他继承的方法也 包括在这里是为了方便。(The 随附的规范 声明已针对 设置接口,但它们不包含 任何附加规定。)

关于 建设者,毫不奇怪, 所有构造函数必须创建 不包含重复项的集合 元素(如上所述)。

从 Map :

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

如果你能实现你的 集合 使用现有的代码,您可以从现有代码中获得的任何好处(例如速度)都会累积到 集合 也。

如果您选择实现 集合 没有 地图 备份时,必须复制设计用于防止重复元素的代码。啊,有趣的讽刺。

也就是说,没有什么能阻止你实现 集合 不同的是。

我猜想,对于实际的应用程序或重要的基准测试,它从来没有出现过重大问题。为什么为了没有真正的好处而把代码复杂化?

另外请注意,在许多JVM实现中,对象大小是四舍五入的,因此实际上可能不会增加大小(我不知道这个例子)。以及 HashMap 可能是在缓存中编译的。如果其他条件相同,则more code=>more cache misses=>性能较低。

我的猜测是,哈希集最初是根据哈希图实现的,目的是为了快速、轻松地完成它。就代码行而言,hashset是hashmap的一部分。

我想它还没有被优化的原因是害怕改变。

然而,浪费比你想象的要严重得多。在32位和64位上,hashset比需要的大4倍,hashmap比需要的大2倍。哈希映射可以用一个数组实现,数组中包含键和值(加上冲突链)。这意味着每个条目有两个指针,或者64位虚拟机上有16个字节。事实上,hashmap每个条目包含一个条目对象,它为指向条目的指针添加了8个字节,为条目对象头添加了8个字节。哈希集也使用每个元素32个字节,但是浪费是4x而不是2x,因为它只需要每个元素8个字节。

是的,你是对的,在那里有少量的浪费。很小,因为每个条目都使用相同的对象 PRESENT (宣布为最终决定)。因此,唯一的浪费就是散列图中每个条目的值。

大多数情况下,我认为他们采用这种方法来实现可维护性和可重用性。(JCF开发人员会想,我们已经测试了hashmap,为什么不重用它呢。)

但是如果你有大量的收藏,而且你是一个记忆怪胎,那么你可以选择放弃更好的选择,比如 Trove 或 Google Collections .

我看了你的问题,想了想你说了些什么。这是我对 HashSet 实施。

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

看看add方法

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

现在让我们来看看看跌回报值

@返回与键关联的上一个值,如果没有键的映射,则返回空值。(一个空返回还可以指示映射以前与空键关联。)

所以 PRESENT 对象只是用来表示集合包含e值。我想你问过为什么不用 null 而不是 现在 . 但是,您将无法区分该条目以前是否在地图上,因为 map.put(key,value) 总是会回来的 无效的 你也无法知道钥匙是否存在。

也就是说,你可以争辩说他们可以使用这样的实现

   public boolean add(E e) {

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

        map.put(e, null);

        return true;

}

我想他们浪费了4个字节来避免计算哈希代码,因为这可能会花费两次(如果要添加密钥的话)。

如果你问他们为什么用 HashMap 这将浪费8个字节(因为 Map.Entry )与其他一些仅使用4个类似条目的数据结构不同,是的,我认为它们之所以这样做是因为您提到的原因。

在搜索了类似这样的页面后,想知道为什么标准实现的效率会比较低,找到了com.carrotsearch.hpc.intopenhashset。

你的问题: 我认为这会浪费4字节(在32位机器上)的条目本身的大小。

只为哈希集的整个数据结构创建一个对象变量,这样做可以避免重新编写整个哈希映射类型的代码。

private static final Object PRESENT = new Object();

所有键都有一个值,即present对象。