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

Question

我知道String类的hashCode()方法不能保证为不同的String-s生成唯一的哈希码.我看到很多使用将String键放入HashMap-s(使用默认的String hashCode()方法).如果地图put替换了之前使用真正不同的String键放入地图的HashMap条目,则大量此类使用可能会导致严重的应用程序问题.

您将遇到String.hashCode()为不同的String-s返回相同值的场景的几率是多少？当密钥是String时,开发人员如何解决此问题？

Answer 1

开发人员不必在HashMap中解决哈希冲突问题,以实现程序的正确性.

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

1. 碰撞是哈希的固有特征,它们必须是.可能值的数量(在您的情况下为字符串,但它也适用于其他类型)远大于整数范围.

2. 哈希的每种用法都有一种处理冲突的方法,Java Collections(包括HashMap)也不例外.

3. Hashing不参与平等测试.确实,相等的对象必须具有相同的哈希码,但反之则不然:许多值将具有相同的哈希码.因此,不要尝试使用哈希码比较作为相等的替代.收藏不.他们使用散列来选择子集合(在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方法的情况下(这意味着你已经编写了一个带有复合值的类,比如名字/姓氏对),事情变得稍微复杂一些.在这里犯错很可能,但这不是火箭科学.首先,要知道这一点:为了确保正确性,您必须做的唯一事情是确保相等的对象产生相同的哈希码.因此,如果为类编写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;
    }
}

Answer 2

我在这里引导您找到答案。虽然使用字符串并不是一个坏主意（@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 为您处理这些事情是明智的。

Answer 3

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

肯定会存在哈希冲突的可能性，因此如果确实存在两个s 具有相同的返回值的情况，那么人们会期望该String.equals方法也会被调用以确保 s真正相等。StringStringhashCode

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

另外要补充的是，这种想法对于 以外的类也适用String，因为Object类本身已经具有hashCode和equals方法。

编辑

String因此，要回答这个问题，不，使用 a作为 a 的键并不是一个坏主意HashMap。