为什么哈希表中的不可变对象如此有效？

Question

为什么哈希表中的不可变对象如此有效？

javaperformancecachinghashmapimmutability

38

我读到了有关 HashMap 的文章。其中提到:

“不可变性也允许缓存不同键的哈希码，这使得整个检索过程非常快速，并建议使用 Java Collection API 提供的 String 和各种包装类(如 Integer) 作为 HashMap 键。”

我不太明白...为什么？

- Toskan

1

由于在 HashMap 中更改存储时的哈希码将导致在该 HashMap 中丢失对该键的访问权限，而且您也可以缓存可变对象的哈希码，因此我认为该句子具有误导性并且有些错误。 - stryba

5

我强烈建议您寻找更好的信息来源，例如Javadoc和Java集合框架文档，网址为http://docs.oracle.com/javase/6/docs/technotes/guides/collections/index.html。那个博客包含了许多事实、语法和拼写错误。您在这里引用的句子完全是文盲的，而暗示HashMap缓存哈希码的表述也是不正确的。 - user207421

@EJP：我也是这么想的。另一个明显的含义是，不可变性是缓存哈希码所必需的，这也不是事实。 - Niklas B.

3

你提供的文章链接实际上是一个充满广告和垃圾信息的站点。我同意其他评论中对该文章技术价值的质疑。 - Steve Kuo

7个回答

10

引用链接博客文章中的内容：

"实现适当的equals()和hashcode()方法的最终对象将作为完美的Java HashMap键，并通过减少碰撞来提高Java hashMap性能。"

我不明白final和equals()如何与哈希冲突有任何关系。这句话让我怀疑文章的可信度。它似乎是一个教条式的Java“智慧”集合。

“不可变性还允许缓存不同键的哈希码，从而使整个检索过程非常快，并建议Java Collection API提供的String和各种包装类（例如Integer）非常适合HashMap键。”

我看到这句话有两种可能的解释，都是错误的：

- HashMap缓存不可变对象的哈希码。这是不正确的。该映射无法找出对象是否“不可变”。 - 对象的不可变性是缓存其自己哈希代码所必需的。理想情况下，对象的哈希值应仅依赖于对象的非变异状态，否则该对象将无法合理地用作键。因此，在这种情况下，作者未能说明一点：如果我们假设对象不改变其状态，那么即使对象是可变的，我们也不必每次重新计算哈希值！

示例：

因此，如果我们真的很疯狂，决定将List用作HashMap的键，并且使哈希值依赖于其内容而不是列表的标识，我们可以决定在每次修改时使缓存的哈希值无效，从而将哈希计算次数限制为列表修改次数。

- Niklas B.

只要确保不修改可变键，就可以在HashMap中使用可变键。但是，可变对象无法可靠地缓存它们的哈希值，因此每次访问映射时都会浪费时间。 - Jeffrey

@Jeffrey：如果数据结构从未被修改，我们可以轻松地设计它，以便我们永远不需要计算哈希超过一次。请检查我的编辑。 - Niklas B.

如果您设计一个数据结构，使其永远不会被修改，那么您正在设计一个不可变的数据结构。如果您必须每次修改可变对象时重新计算哈希值，那么开销可能比每次调用hashCode时重新计算还要糟糕。 - Jeffrey

@Jeffrey：每个理智的实现都会在需要时计算hashCode并设置一个标志来表示hashCode已被计算。下次修改结构时，将重置该标志，以便hashCode知道它下一次必须重新计算。我不知道Java是否是这样做的，但许多其他语言也是这样工作的。它不会引入额外开销，仍然不需要每次重新计算哈希值。认为这种缓存需要不可变性是完全错误的。 - Niklas B.

抱歉，可能我误读了你的话。我本来以为你在谈论每次修改都要重新计算哈希值的问题。你的想法很好，点赞！ - Jeffrey

6

很简单。由于不可变对象随时间不会改变，因此只需要执行一次哈希码的计算。再次计算将得到相同的值。因此，在构造函数（或懒加载）中计算哈希码并将其存储在字段中是常见的做法。然后hashcode函数仅返回字段的值，这确实非常快。

- Roland Illig

1

在Java中，基本上通过使类不可扩展并且对象中的所有操作理想情况下不改变对象的状态来实现不可变性。如果您查看String的操作（如replace()），它不会更改您正在操作的当前对象的状态，而是提供一个替换字符串的新String对象。因此，如果您将这些对象保持为键，则状态不会更改，因此哈希码也保持不变。因此，在检索期间缓存哈希码将具有性能效益。

- raddykrish

1

将哈希表想象成一个编号的大盒子数组。编号是哈希码，而盒子按编号排序。

如果对象不能更改，则哈希函数始终会产生相同的值。因此，对象将始终保留在它的盒子中。

现在假设一个可变对象。在添加到哈希表后，它被更改了，所以现在它坐在错误的盒子里，就像琼斯夫人嫁给了道先生，现在也叫道，但在许多记录中仍然叫琼斯。

- user unknown

1

不可变类是不可修改的，这就是为什么它们被用作Map中的键。

举个例子 -

    StringBuilder key1=new StringBuilder("K1");
    StringBuilder key2=new StringBuilder("K2");
    
    Map<StringBuilder, String> map = new HashMap<>();
    map.put(key1, "Hello");
    map.put(key2, "World");
    
    key1.append("00");
    System.out.println(map); // This line prints - {K100=Hello, K2=World}

你可以看到，由于不经意间对其进行了更改，导致可变类StringBuilder对象K1作为映射键值丢失。如果您使用不可变类作为Map家族成员的键，则不会发生这种情况。

- Aniruddha Sardar

0

哈希表只有在对象的哈希码在存储在表中时永远不会改变时才能正常工作。这意味着哈希码不能考虑到对象在表中可能发生的任何变化。如果对象的最有趣的方面是可变的，那么就意味着：

哈希码将不得不忽略对象的大部分有趣方面，从而导致许多哈希冲突，或者...
拥有哈希表的代码将不得不确保其中的对象在存储在哈希表中时不会受到可能改变它们的任何影响。

如果Java哈希表允许客户端提供一个EqualityComparer（就像.NET字典一样），那么知道哈希表中对象的某些方面不会意外更改的代码可以使用考虑到这些方面的哈希码，但在Java中实现这一点的唯一方法是将存储在哈希码中的每个项都包装起来。这样的包装可能并不是世界上最邪恶的事情，因为包装器能够以EqualityComparer无法做到的方式缓存哈希值，并且还可以缓存进一步的相等相关信息[例如，如果被存储的东西是嵌套集合，则计算多个哈希码并确认所有哈希码匹配后再进行任何元素的详细检查可能是值得的]。

- supercat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeffrey · Accepted Answer

String#hashCode：

private int hash;

...

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

由于 String 的内容永远不会改变，该类的创建者选择在计算一次哈希后缓存它。这样，不会浪费时间重新计算相同的值。