糟糕的想法在HashMap中使用String键？
我明白String类的hashCode（）方法不能保证为不同的String-s生成唯一的哈希码。 我看到很多将String键放入HashMap-s的用法（使用默认的String hashCode（）方法）。 如果一个地图put了一个以前放置在地图上的HashMap条目，并且使用了一个真正的不同的String键，那么很多这种用法可能会导致重大的应用程序问题。
你会遇到什么情况，String.hashCode（）为不同的String-s返回相同的值？ 密钥是string时，开发人员如何解决此问题？
开发人员不必在HashMap中解决散列冲突的问题，以实现程序的正确性。
这里有几个关键的东西需要理解：
- 碰撞是散列的一个固有特性，它们必须是。 可能值的数量（在你的情况下是string，但也适用于其他types）远远大于整数范围。
- 散列的每一种用法都有处理冲突的方法，Java Collections（包括HashMap）也不例外。
- 散列不参与平等testing。 平等的对象必须具有相同的哈希码，但事实并非如此：许多值将具有相同的哈希码。 所以不要尝试使用散列码比较来取代平等。 集合不。 他们使用散列来select一个子集合（在Java集合世界中称为一个存储桶），但他们使用.equals（）来实际检查是否相等。
- 您不但不必担心在集合中导致不正确结果的冲突，而且对于大多数应用程序，您通常也不必担心性能 – Java散列集合在pipe理散列码方面做得非常好。
- 更好的是，对于你问到的问题（string作为键），你甚至不用担心哈希码本身，因为Java的String类生成了一个相当不错的哈希码。 所以大部分提供的Java类。
更多的细节，如果你想要它：
散列的方式（特别是像Java的HashMap这样的散列集合，这就是你所问的）是这样的：
-
HashMap将您给定的值存储在称为桶的子集合集合中。 这些实际上是作为链接列表实现的。 这些数量有限：iirc，默认启动16，随着你把更多的物品放到地图上，数字会增加。 应该总是有更多的水桶比价值。 举一个例子，使用默认值，如果将100个条目添加到HashMap中，则会有256个存储桶。
-
在映射中可用作键的每个值都必须能够生成一个称为散列码的整数值。
-
HashMap使用这个哈希码来select一个桶。 最后，这意味着以整数值为
modulo数桶的数量，但在此之前，Java的HashMap有一个内部方法（称为hash()），调整哈希代码，以减less一些已知的聚集来源。 -
查找值时，HashMap会select该存储桶，然后使用
.equals()通过线性search链表来search单个元素。
所以：你不必为了正确性而绕过碰撞，而且你通常不需要担心它们的性能，而且如果你使用的是原生的Java类（比如String），你不必担心生成哈希码值。
在你必须编写你自己的hashcode方法的情况下（这意味着你已经写了一个复合值的类，比如名字/姓氏），事情会变得稍微复杂一些。 这里很可能会弄错，但这不是火箭科学。 首先，要知道这一点：为了保证正确性，你唯一要做的就是保证相等的对象产生相同的hashcode。 所以，如果你为你的类写了一个hashcode（）方法，你还必须编写一个equals（）方法，并且你必须在每个方法中检查相同的值。
有可能写一个hashcode（）方法，这个方法不好但是正确，我的意思是说它会满足“相等的对象必须产生相同的hashcode”的约束，但是仍然performance很差，因为有很多的冲突。
规范退化的最坏情况就是编写一个方法，对所有情况简单地返回一个常数值（例如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; } }
我强烈怀疑HashMap.put方法并不通过查看String.hashCode来确定键是否相同。
肯定会有散列冲突的机会，所以人们会期望String.equals方法也会被调用来确保String是真正相等的，如果确实存在两个String都有的情况从hashCode返回相同的值。
因此，当且仅当hashCode返回的值相等且equals方法返回true ，才会将新的键String判断为与已存在于HashMap中的String相同的键String 。
还要补充一点，这个思想对于String以外的类也是如此，因为Object类本身已经有了hashCode和equals方法。
编辑
所以，为了回答这个问题，不，使用String作为HashMap的关键字不是一个坏主意。
这不是一个问题，它只是哈希表的工作方式。 对于所有不同的string都有明确的哈希码是不可能的，因为比整数有更多不同的string。
正如其他人写的，散列冲突通过equals（）方法解决。 这可能造成的唯一问题是哈希表的退化，导致性能不佳。 这就是为什么Java的HashMap具有一个加载因子 ，即桶与插入元素之间的比率，当超过时，将导致表的重新哈希值为桶的数量的两倍。
这通常工作得很好，但只有散列函数是好的，也就是说，不会超过统计上预期的特定input集的碰撞次数。 String.hashCode()在这方面很好，但并不总是如此。 据说 ，在Java 1.2之前，它只包含了每一个字符。 这是更快，但造成所有string共享每个N字符的可预测的冲突 – 非常糟糕，如果你不够经常的input，或者如果有人想对你的应用程序的DOS攻击。
我指示你在这里的答案。 尽pipe使用string（@CPerkins解释为什么完美）并不是一个坏主意，但是将值存储在具有整数键的hashmap中是更好的 ，因为它通常更快 （尽pipe不明显）并且具有更低的机会（实际上没有机会）碰撞。
在每种情况下，使用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，因为string的数量是没有限制的（对于可以存储在HashMap的键的数量没有理论上的限制）。 如果你使用一个long （甚至是一个float ），冲突将是不可避免的，因此不会比string“更好”。 但是，即使是散列冲突， put()和get()也会始终input/获取正确的键值对（请参阅下面的编辑）。
最后真的没关系，所以尽量使用方便。 但是，如果方便没有区别，而且你不打算有超过2 ^ 32的条目，我build议你使用ints作为键。
编辑
虽然上面的说法是正确的，但出于性能的原因，不要使用“StringKey”.hashCode（）生成一个键来代替原始的String键 – 两个不同的string可以具有相同的hashCode，导致覆盖put()方法。 Java的HashMap的实现足够聪明，可以自动处理具有相同散列码的string（实际上是任何types的键），所以让Java为您处理这些事情是明智的。
你在谈论哈希碰撞。 散列冲突是一个问题，不pipetypes是hashCode。 所有使用hashCode（例如HashMap）的类都可以处理散列冲突。 例如，HashMap可以存储每个桶的多个对象。
除非你自己调用hashCode，否则不要担心。 哈希碰撞虽然很less，但不会破坏任何东西。
