在哈希表中查找冲突

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相同.对不起,如果我听起来像,但我不是要求代码或任何东西,只是对问题的一些想法/提示.任何评论都非常感谢.谢谢

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).但是为这种风格生成五个例子(所有相同的哈希)是否容易？

Answer 2

根据维基百科关于Java的字符串哈希算法的文章(与你提出的算法相同):

与任何一般的散列函数一样,碰撞也是可能的.例如,字符串"FB"和"Ea"具有相同的散列值.String的hashCode()实现使用素数31,'a'和'B'之间的差值仅为31,因此计算为70×31 + 66 = 69×31 + 97.