java - 在哈希表中查找冲突

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)。但是为这种风格生成 5 个例子(都是相同的散列)容易吗？