查找散列表中的冲突

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

按照Wikipedia article on Java's string hashing algorithm（这是一样的，你呈现算法）：

与任何一般散列函数，碰撞是可能的。例如，对于 示例，字符串“FB”和“Ea”具有相同的散列值。所述 hashCode（）方法执行字符串的使用素数31和 'a' 和 'B' 之间的差 只是31，因此计算为70×31 + 66 = 69×31 + 97

Answer 2

Java字符串可以包含一个零字符（"\0"），所以以下所有会返回相同的值：

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

这里的证明（感谢埃里克的裁判这是使用的哈希）：

> 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）。但是为这种风格生成示例（所有相同的散列）很容易吗？