38

所以我读到了HashMap。有人指出：

“不变性还允许缓存不同键的哈希码，这使得整个检索过程非常快，并表明IntegerJava 集合 API 提供的 String 和各种包装类（例如 ）是非常好的HashMap键。”

我不太明白……为什么？

4

7 回答 7

36

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;
}

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

于 2012-04-26T23:43:50.093 回答
10

引用链接的博客条目：

具有正确 equals() 和 hashcode() 实现的最终对象将充当完美的 Java HashMap 键，并通过减少冲突来提高 Java hashMap 的性能。

我看不到两者如何final以及equals()与哈希冲突有什么关系。这句话引起了我对文章可信度的怀疑。它似乎是教条式的 Java“智慧”的集合。

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

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

  • HashMap缓存不可变对象的哈希码。这是不正确的。地图无法确定对象是否“不可变”。
  • 对象缓存其自己的哈希码需要不变性。理想情况下，一个对象的哈希值应该始终只依赖于对象的非变异状态，否则该对象不能被明智地用作键。所以在这种情况下，作者也没有说明一点：如果我们假设我们的对象没有改变它的状态，我们也不必每次都重新计算哈希值，即使我们的对象是可变的！

例子

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

于 2012-04-26T23:46:13.460 回答
6

这很简单。由于不可变对象不会随时间变化，因此它只需要执行一次哈希码的计算。再次计算将产生相同的值。因此，通常在构造函数（或惰性）中计算哈希码并将其存储在字段中。然后该hashcode函数只返回该字段的值，这确实非常快。

于 2012-04-26T23:45:28.843 回答
1

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

于 2012-04-26T23:46:40.827 回答
1

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

现在如果对象不能改变，散列函数将总是重现相同的值。因此，该对象将始终留在它的盒子里。

现在假设一个可变对象。它在添加到散列后被更改，所以现在它放在错误的盒子里，就像琼斯夫人碰巧嫁给了 Doe 先生，现在也被命名为 Doe，但在许多寄存器中仍然命名为 Jones。

于 2012-04-26T23:47:48.350 回答
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}

您会看到插入到映射中的键 K1（它是可变类 StringBuilder 的对象）由于无意更改而丢失。如果您使用不可变类作为 Map 系列成员的键，则不会发生这种情况。

于 2020-07-20T17:06:14.843 回答
0

仅当对象的哈希码在存储在表中时永远不会更改时，哈希表才会起作用。这意味着哈希码不能考虑对象在表中时可能更改的任何方面。如果一个对象最有趣的方面是可变的，这意味着：

  • 哈希码将不得不忽略对象的大部分有趣方面，从而导致许多哈希冲突，或者......

  • 拥有哈希表的代码必须确保其中的对象在存储在哈希表中时不会暴露于任何可能改变它们的东西。

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

于 2013-12-26T16:48:29.630 回答