在 HashMap 中使用 String 键是个坏主意吗？

我理解 String 类的 HashCode ()方法是 没有，它保证为不同的 String-s 生成惟一的哈希代码。我看到很多将 String 键放入 HashMap-s 中的用法(使用默认的 String hashCode ()方法)。如果映射 put取代了以前用一个真正不同的 String 键放到映射上的 HashMap 条目，那么这种使用可能会导致严重的应用程序问题。

对于不同的 String-s，String.hashCode ()返回相同值的可能性有多大？当键是 String 时，开发人员如何解决这个问题？

79002 次浏览
小开

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

肯定会有一个 散列碰撞的机会，所以我们可以期望 String.equals方法也会被调用，以确保 String是真正相等的，如果确实存在这样一种情况，即两个 String具有从 hashCode返回的相同值。

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

另外，这个想法也适用于 String以外的类，因为 Object类本身已经有了 hashCode和 equals方法。

剪辑

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

小开

你说的是散列冲突。无论正在使用 hashCode 的类型是什么，散列冲突都是一个问题。所有使用 hashCode 的类(例如 HashMap)都可以很好地处理散列冲突。例如，HashMap 可以在每个桶中存储多个对象。

除非您自己调用 hashCode，否则不要担心它。

小开
最佳答案

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

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

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

  2. 散列的每种用法都有处理冲突的方法，Java 集合(包括 HashMap)也不例外。

  3. 散列不涉及相等性测试。的确，相等的对象必须有相等的哈希码，但是相反的情况就不一样了: 许多值都有相同的哈希码。所以不要尝试使用散列码比较来替代相等。收集不会。它们使用哈希来选择一个子集合(在 JavaCollectionsworld 中称为 bucket) ，但是它们使用。Equals ()实际检查是否相等。

  4. 不仅不必担心冲突会导致集合中出现不正确的结果，而且对于大多数应用程序来说，通常也不必担心性能—— Java 散列集合在管理哈希代码方面做得相当不错。

  5. 更好的是，对于您询问的情况(作为键的字符串) ，您甚至不必担心散列码本身，因为 Java 的 String 类生成了一个相当好的散列码。所提供的大多数 Java 类也是如此。

更多细节，如果你想知道的话:

散列的工作方式(特别是像 Java 的 HashMap 这样的散列集合)是这样的:

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

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

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

  • 在查找值时，HashMap 选择 bucket，然后使用 .equals()对链表进行线性搜索来搜索单个元素。

所以: 您不必为了正确性而绕过冲突，而且通常也不必担心它们的性能，如果您使用的是本机 Java 类(比如 String) ，那么您也不必担心生成 hashcode 值。

如果您必须编写自己的 hashcode 方法(这意味着您已经编写了一个具有复合值的类，比如名/姓对) ，那么事情就会稍微复杂一些。这里很可能出错，但这不是火箭科学。首先，要知道: 为了确保正确性，您必须做的唯一一件事就是确保相同的对象产生相同的散列码。因此，如果为类编写 hashcode ()方法，则还必须编写 equals ()方法，并且必须检查每个类中的相同值。

编写一个散列码()方法是可能的，这个方法很糟糕，但是是正确的，我的意思是它可以满足“相等的对象必须产生相等的散列码”约束，但是由于存在大量的冲突，它的性能仍然很差。

最糟糕的情况就是写一个方法，在所有情况下返回一个常量值(例如，3)。这意味着每个值将被散列到同一个桶中。

它仍然是 工作，但是性能会降低到链表的性能。

显然，您不会编写如此糟糕的 hashcode ()方法。如果您正在使用一个像样的 IDE，它可以为您生成一个 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;
}
}
小开

这不是问题，这只是哈希表的工作方式。可以证明，不可能为所有不同的字符串都使用不同的散列码，因为不同的字符串比整数多得多。

正如其他人所写的，哈希冲突是通过 equals ()方法解决的。这可能导致的唯一问题是散列表的退化，从而导致糟糕的性能。这就是 Java 的 HashMap 具有 负荷系数的原因，负荷系数是桶和插入元素之间的比率，如果超过这个比率，将导致用两倍于桶的数量重新散列表。

这通常可以很好地工作，但是只有当散列函数很好时，也就是说，对于您的特定输入集，不会导致超过统计学预期的冲突数量。String.hashCode()在这方面是好的，但这并不总是如此。在 Java 1.2之前，据说是的只包含非 h 字符。这样更快，但是对于所有字符串共享的每个非 h 字符来说都会造成可预测的冲突——如果你运气不好，没有这样的常规输入，或者有人想对你的应用程序进行 DOS 攻击，那么这将是非常糟糕的。

小开

我告诉你答案 给你。虽然使用字符串不是 很糟糕的想法(@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，因为字符串的数量没有限制(理论上也没有可以存储在 HashMap中的键的数量的限制)。如果使用 long(甚至 float) ，冲突将是不可避免的，因此没有比字符串更好的了。然而，即使有散列冲突，put()和 get()也总是放置/获取正确的键值对(见下面的编辑)。

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

剪辑

虽然上面的确是真的，但是千万不要使用“ StringKey”。由于性能原因，hashCode ()生成一个密钥来代替原来的 String密钥-2个不同的字符串可能具有相同的 hashCode，从而导致对 put()方法的覆盖。Java 的 HashMap实现足够聪明，可以使用相同的散列码自动处理字符串(实际上是任何类型的键) ，所以让 Java 为您处理这些事情是明智的。


提交答案