71

我知道 String 类的hashCode()方法不能保证为不同的 String-s 生成唯一的哈希码。我看到很多将 String 键放入 HashMap-s 的用法（使用默认的 String hashCode() 方法）。如果映射put替换了之前使用真正不同的字符串键放入映射的 HashMap 条目，则很多这种用法可能会导致严重的应用程序问题。

您遇到 String.hashCode() 为不同的 String-s 返回相同值的情况的几率是多少？当键是字符串时，开发人员如何解决这个问题？

4

5 回答 5

117

开发人员不必为了实现程序正确性而解决 HashMap 中的哈希冲突问题。

这里有几个关键的事情要理解：

  1. 冲突是散列的固有特征，而且必须如此。可能值的数量（在您的情况下为字符串，但它也适用于其他类型）远远大于整数的范围。

  2. 哈希的每种用法都有处理冲突的方法，Java 集合（包括 HashMap）也不例外。

  3. 哈希不参与相等性测试。确实，相等的对象必须具有相等的哈希码，但反之则不然：许多值将具有相同的哈希码。所以不要尝试使用哈希码比较来代替相等。收藏品没有。他们使用散列来选择一个子集合（在 Java 集合世界中称为存储桶），但他们使用 .equals() 来实际检查是否相等。

  4. 您不仅不必担心冲突会导致集合中的错误结果，而且对于大多数应用程序，您*通常*不必担心性能 - Java 哈希集合在管理哈希码方面做得很好。

  5. 更好的是，对于您询问的情况（字符串作为键），您甚至不必担心哈希码本身，因为 Java 的 String 类会生成一个非常好的哈希码。大多数提供的 Java 类也是如此。

更多细节，如果你想要的话：

散列的工作方式（特别是在像 Java 的 HashMap 这样的散列集合的情况下，这是您所询问的）是这样的：

  • HashMap 将您给它的值存储在一个子集合的集合中，称为存储桶。这些实际上是作为链表实现的。这些数量有限：iirc，默认启动 16 个，并且随着您将更多项目放入地图中，数量会增加。桶的数量应该总是多于价值。举一个例子，使用默认值，如果您向 HashMap 添加 100 个条目，则将有 256 个桶。

  • 每个可以用作映射中键的值都必须能够生成一个整数值，称为哈希码。

  • HashMap 使用这个哈希码来选择一个桶。最终，这意味着取整数值modulo作为桶的数量，但在此之前，Java 的 HashMap 有一个内部方法（称为hash()），它调整哈希码以减少一些已知的聚集源。

  • 查找值时，HashMap 会选择存储桶，然后通过链表的线性搜索来搜索单个元素，使用.equals().

所以：您不必为了正确性而解决冲突，通常不必担心它们的性能，如果您使用的是本地 Java 类（如 String），则不必担心生成哈希码值。

如果您必须编写自己的哈希码方法（这意味着您编写了一个具有复合值的类，例如名字/姓氏对），事情会变得稍微复杂一些。这里很可能会出错，但这不是火箭科学。首先，要知道这一点：为了确保正确性，您必须做的唯一一件事就是确保相等的对象产生相等的哈希码。所以如果你为你的类写了一个 hashcode() 方法，你还必须写一个 equals() 方法，并且你必须检查每个方法中的相同值。

可以编写一个不好但正确的 hashcode() 方法，我的意思是它会满足“相等的对象必须产生相等的哈希码”约束，但由于有很多冲突，仍然表现得很差。

典型的退化最坏情况是编写一个方法，该方法在所有情况下都简单地返回一个常量值（例如，3）。这意味着每个值都将被散列到同一个桶中。

它仍然可以工作，但性能会下降到链表的性能。

显然，你不会写出这么糟糕的 hashcode() 方法。如果您使用的是不错的 IDE，它能够为您生成一个。由于 StackOverflow 喜欢代码，这里是上面 firstname/lastname 类的代码。


public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}
于 2009-10-04T14:53:07.420 回答
5

我将您引向此处的答案。虽然使用字符串不是一个坏主意（@CPerkins 完美地解释了原因），但使用整数键将值存储在哈希图中会更好，因为它通常更快（虽然不明显）并且机会更低（实际上，没有机会）的碰撞。

请参阅这张在每种情况下使用 216553 键的冲突图表，（从这篇文章中窃取，重新格式化以供我们讨论）

Hash           Lowercase      Random UUID  Numbers 
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis*
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis***
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis***
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis

Avg Time per key    0.8ps       2.5ps         0.44ps
Collisions (%)      0.002%      0.002%         0%

当然，整数的数量限制为 2^32，因为字符串的数量没有限制（理论上可以存储的键数量没有限制 a HashMap）。如果您使用 a long（甚至 a float），冲突将是不可避免的，因此没有比字符串“更好”的了。但是，即使有哈希冲突，put()也get()总是会放置/获取正确的键值对（参见下面的编辑）。

最后，真的没关系，所以使用任何更方便的东西。但是如果方便没有区别，并且您不打算拥有超过 2^32 个条目，我建议您使用intsas 键。

编辑

虽然以上内容绝对正确，但出于性能原因，切勿使用“StringKey”.hashCode() 生成密钥来代替原始String密钥 - 2 个不同的字符串可能具有相同的 hashCode，从而导致覆盖您的put()方法。Java 的实现HashMap非常智能，可以自动处理具有相同哈希码的字符串（实际上是任何类型的键），因此让 Java 为您处理这些事情是明智的。

于 2013-06-03T13:42:00.387 回答
4

我强烈怀疑该HashMap.put方法不能仅通过查看来确定密钥是否相同String.hashCode。

肯定会有散列冲突的可能性，所以人们会期望该String.equals方法也将被调用以确保Strings 真正相等，如果确实存在两个Strings 具有从返回的相同值的情况hashCode.

因此，只有当返回的值相等且方法返回时，String才会判断新键与ifString中已经存在的键相同。HashMaphashCodeequalstrue

还要补充一点，这种想法也适用于除 之外String的类，因为Object类本身已经具有hashCodeandequals方法。

编辑

因此，要回答这个问题，不，将 aString用作 a 的密钥并不是一个坏主意HashMap。

于 2009-10-04T14:42:55.207 回答
4

这不是问题，它只是哈希表的工作方式。事实证明，所有不同的字符串都有不同的哈希码是不可能的，因为不同的字符串比整数要多得多。

正如其他人所写，哈希冲突是通过 equals() 方法解决的。这可能导致的唯一问题是哈希表的退化，从而导致性能下降。这就是为什么 Java 的 HashMap 有一个负载因子，即桶和插入元素之间的比率，当超过该比率时，将导致使用两倍数量的桶对表进行重新散列。

这通常工作得很好，但前提是散列函数是好的，即不会导致超过您的特定输入集的统计预期碰撞次数。String.hashCode()在这方面是好的，但并非总是如此。据称，在 Java 1.2 之前，它只包含每个第 n 个字符。这更快，但会导致共享每个第 n 个字符的所有 String 发生可预测的冲突 - 如果您不走运而无法进行此类常规输入，或者如果有人想对您的应用程序进行 DOS 攻击，那就太糟糕了。

于 2009-10-04T15:20:43.980 回答
2

您正在谈论哈希冲突。无论使用 hashCode 的类型如何，哈希冲突都是一个问题。所有使用 hashCode（例如 HashMap）的类都可以很好地处理散列冲突。例如，HashMap 可以在每个桶中存储多个对象。

除非您自己调用 hashCode，否则不要担心。哈希冲突虽然很少见，但不会破坏任何东西。

于 2009-10-04T14:50:46.927 回答