在HashMap中使用String键的坏主意？

Question

我知道String类的hashCode（）方法
不能 保证为不同的String-s生成唯一的哈希码。我看到了很多将String键放入HashMap-s的用法（使用默认的String
hashCode（）方法）。如果put地图使用真正不同的String键替换了先前放置在地图上的HashMap条目，那么很多这种用法可能会导致重大的应用程序问题。

在String.hashCode（）对于不同的String-s返回相同值的情况下，您遇到的几率是多少？当键是字符串时，开发人员如何解决此问题？

Answer 1

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

这里有一些关键的事情要理解：

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

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

3. 哈希不参与相等性测试。确实，相等的对象必须具有相等的哈希码，但事实并非如此：许多值将具有相同的哈希码。因此，请勿尝试使用哈希码比较来替代相等性。收藏没有。他们使用哈希选择一个子集合（在Java Collections世界中称为存储桶），但是他们使用.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;
    }
}