查找散列表中的衝突

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）。但是爲這種風格生成示例（所有相同的散列）很容易嗎？