在哈希表中寻找碰撞

Question

我正在为我的数据结构期末考试复习，并在去年的期末考试中遇到了一个问题。我已经花了过去三个小时来解决这个问题，除了通过试错之外，我仍然无法找出解决方法。以下是问题：

“假设您的哈希表大小为31，常量g也为31，并且您使用以下哈希代码

int hash = 0;
int n = s.length();
for (int i = 0; i < n; i++)
   hash = g * hash + s.charAt(i);

并且您使用分离链接解决冲突。列出五个不同的名称，这些名称将哈希到表中的同一位置。

考虑到哈希表的大小为31，与常数g相同，我认为必须有某种技巧（可能涉及取模运算）来解决这个问题。对不起，如果我听起来像是在要代码或其他东西，但我只是想了解一些关于这个问题的想法/提示。任何意见都将不胜感激。谢谢。

- James Durbin

Answer 1

Java中的字符串可以包含零字符（"\0"），因此以下所有内容将生成相同的哈希值：

"a"
"\0a"
"\0\0a"
"\0\0\0a"
"\0\0\0\0a"

以下是证明（感谢 Eric 提供的哈希值）：

> cat Foo.java
class Foo {
    public static void main(String[] args) {                                    
        System.out.println("a".hashCode());                                     
        System.out.println("\0a".hashCode());                                   
        System.out.println("\0a".length());
        System.out.println("\0a".equals("a"));
    }                                                                           
}           
> javac Foo.java                                        
> java Foo                                                       
97
97
2
false

我觉得这不是预期的答案。

此外，如果这是一场考试，我怀疑我能记住ASCII码。因此，使用其他答案中的样式序列的替代方法是：

"\002\000"
"\001\037"

等等（这些是八进制三元组 - 上面两个都哈希到62）。但是生成五个样例（所有哈希相同）对于这种风格来说容易吗？

- andrew cooke

---

是的，我不认为这是预期的答案哈哈，但仍然非常感谢！我学到了关于零字符的一个新知识，所以这非常棒。 - James Durbin

Answer 2

根据Java字符串哈希算法的维基百科文章（与您提供的算法相同）：

与任何通用哈希函数一样，冲突是可能的。例如，字符串“FB”和“Ea”具有相同的哈希值。String的hashCode()实现使用质数31和'a'和'B'之间的差值仅为31，因此计算公式为70 × 31 + 66 = 69 × 31 + 97。

- Eric J.

---

顺便提一下，这种哈希实现方式会让Java容易受到DoS攻击！请参考http://www.ocert.org/advisories/ocert-2011-003.html、http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/或者通过谷歌搜索使用哈希映射进行的DoS攻击。 - yshavit

@yshavit：有趣。我以前没有考虑过这个问题，但它非常合理。 - Eric J.

String.hashCode 生成冲突的更多方法：http://david-soroko.blogspot.co.uk/2015/06/generating-collisions-in-stringhashcode.html - David Soroko