为什么Java中的String.hashCode（）有很多冲突？

为什么String.hashcode（）有这么多冲突？

我在jdk1.6中读取String.hashCode（），下面是代码

public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; } 

这对我来说很混乱，因为它有很多冲突; 虽然它不需要是唯一的（我们仍然可以依赖于equals（）），但是更少的冲突意味着更好的性能而无需访问链表中的条目。

假设我们有两个字符，那么只要我们能找到两个匹配下面的方程的字符串，那么我们就会有相同的hashcode（）

 a * 31 +b = c * 31 +d 

很容易得出结论， (ac) * 31 = db举一个简单的例子是make ac = 1和db = 31; 所以我写下面的代码进行简单测试

 public void testHash() { System.out.println("A:" + (int)'A'); System.out.println("B:" + (int)'B'); System.out.println("a:" + (int)'a'); System.out.println("Aa".hashCode() + "," + "BB".hashCode()); System.out.println("Ba".hashCode() + "," + "CB".hashCode()); System.out.println("Ca".hashCode() + "," + "DB".hashCode()); System.out.println("Da".hashCode() + "," + "EB".hashCode()); } 

它将打印在结果下面，这意味着所有字符串都具有相同的hashcode（），并且它很容易在循环中完成。

 A:65 B:66 a:97 2112,2112 2143,2143 2174,2174 2205,2205 

更糟糕的是，假设我们在字符串中有4个字符，根据算法，假设前2个字符产生a2，第2个字符产生b2; 因此，哈希码仍然是a2 * 31^2 + b2 ，a2和b2在2个字符串之间相等，我们将获得更多带有hashcode（）冲突的字符串。 这样的例子是“AaAa”，“BBBB”等等; 那么我们将有6个字符，8个字符……

假设大多数时候我们在字符串中使用ascii表中的字符将在hashmap或hashtable中使用，那么这里选择的素数31肯定太小;

一个简单的解决方法是使用更大的素数（幸运的是，257是素数）可以避免这种冲突。 当然，选择一个太大的数字会导致返回的int值溢出，如果字符串很长，但我假设大多数时候用作键的字符串不是那么大？ 当然，它仍然可以返回一个很长的值来避免这种情况。

下面是我对betterhash（）的修改版本，它可以通过运行将在值下面打印的代码轻松解决这些冲突，这对解决这个问题很有效。

 16802,17028 17059,17285 17316,17542 17573,17799 

但为什么jdk没有解决它？ 谢谢。

 @Test public void testBetterhash() { System.out.println(betterHash("Aa") + "," + betterHash("BB")); System.out.println(betterHash("Ba") + "," + betterHash("CB")); System.out.println(betterHash("Ca") + "," + betterHash("DB")); System.out.println(betterHash("Da") + "," + betterHash("EB")); } public static int betterHash(String s) { int h = 0; int len = s.length(); for (int i = 0; i < len; i++) { h = 257*h + s.charAt(i); } return h; } 

Answer 1

我刚刚练习了58,000个英语单词（在这里找到），全都是小写的，第一个字母大写。 知道有多少相撞？ 二：“兄弟姐妹”和“德黑兰”（“德黑兰”的另一种拼写）。

就像你一样，我采用了一个子域（在我的情况下可能是一个）可能的字符串并分析了它的hashCode冲突率，并发现它是示例性的。 谁能说你的可选字符串的任意子域是比我的优化更好的选择？

编写此类的人必须这样做，因为他们无法预测（也不因此优化）其用户将字符串用作键的子域。 所以他们选择了一个哈希函数，它在整个字符串域上均匀分布。

如果你有兴趣，这是我的代码（它使用Guava）：

  List words = CharStreams.readLines(new InputStreamReader(StringHashTester.class.getResourceAsStream("corncob_lowercase.txt"))); Multimap wordMap = ArrayListMultimap.create(); for (String word : words) { wordMap.put(word.hashCode(), word); String capitalizedWord = word.substring(0, 1).toUpperCase() + word.substring(1); wordMap.put(capitalizedWord.hashCode(), capitalizedWord); } Map> collisions = Maps.filterValues(wordMap.asMap(), new Predicate>() { public boolean apply(Collection strings) { return strings.size() > 1; } }); System.out.println("Number of collisions: " + collisions.size()); for (Collection collision : collisions.values()) { System.out.println(collision); } 

编辑

顺便说一句，如果你很好奇，与String.hashCode的1相比，你的哈希函数的相同测试有13次冲突。

Answer 2

对不起，我们需要对这个想法投入一些冷水。

1. 您的分析太简单了。 你似乎已经挑选了一系列字符串，旨在certificate你的观点。 这并不表明在所有字符串的域中冲突的数量（统计上）高于预期。

2. 没有人会想到 String.hashCode是高度无冲突的。 它的设计并没有考虑到这一点。 （如果你想要高度无冲突散列，那么使用加密散列算法……并支付费用。）String.hashCode（）被设计为在所有字符串的域中相当不错……并且速度很快 。

3. 假设你可以陈述一个更强的案例，这不是说明它的地方。 您需要向重要人员提出此问题 – Oracle的Java工程团队。

4. Java工程团队将权衡这种变化的优势与实现它的成本，为他们以及Java的每个其他用户 。 最后一点可能足以杀死这个石头死的想法。

---

^{（“高度无冲突散列”，是一个想法/术语，我为了这个答案而撤出了。抱歉。但是，要点是，2个字符串的哈希码冲突的概率应该与相关性无关例如，“AA”和“bz”由于具有相同的长度而相关。显然，这个想法需要更多的思考。而且我所谈论的意义上的“相关性”也很明显。不可测量……有点像Kolmogorov复杂性 。）}

Answer 3

散列时碰撞是不可避免的。 hashCode()方法返回一个整数，该整数用作数组的索引，该数组是具有相同哈希码的所有对象的存储桶。 equals(Object)方法用于将目标对象与存储桶中的每个对象进行比较，以识别完全匹配的对象（如果存在）。

最终， hashCode()方法只需要快速而不是太弱（即导致太多的冲突），其中太弱是非常模糊的度量。

Answer 4

它非常高效但也很简单。 所有可能的小写（ASCII）字最多六个字母或所有数字最多六个数字长都有一个唯一的hashCode（）。 即hashCode就像一个基数31。 使用更大的数字有其自身的问题。 257因子会使每第8位不是特别随机，因为所有ASCII字符都有0个最高位。 较大的因素将导致五个和六个数字/字母单词的重复哈希码。

如果无法更改散列算法，可能是最大的问题。 无论采用何种方法，都可能出现这种情况，这是一个非常糟糕的选择，并且可能对您的用例而言不是最佳选择。

也许最大的问题是拒绝服务攻击造成病态病例，通常非常罕见很常见。 例如，攻击Web服务器的方法是使用具有相同hashCode的密钥填充高速缓存，例如每次计算的0。 这会导致HashMap退化为链表。

解决这个问题的一个简单方法是使哈希算法未知，可能会发生变化。 作为它的立场，最好的可能是使用TreeMap（它支持自定义比较，虽然在这种情况下默认会很好）