Kollisionen in Hash-Tabelle finden

Question

Ich war für meine Datenstrukturen Abschlussprüfung überprüfen, und ich stieß auf eine Frage im Finale des vergangenen Jahres. Nachdem ich in den letzten drei Stunden daran gearbeitet hatte, konnte ich immer noch keine Lösung finden, außer durch Versuch und Irrtum. Hier ist die Frage:

„Nehmen wir an, dass die Größe der Hash-Tabelle 31 ist die Konstante g ist auch 31, und dass Sie verwenden, um den folgenden Hash-Code

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

und dass Sie separate Verkettungs verwenden zu lösen Kollisionen. Listen Sie fünf verschiedene Namen auf, die zum selben Ort in der Tabelle hashen würden. "

Ich denke, es muss eine Art von Tricks, möglicherweise mit dem Modulo-Operator, um dieses Problem zu lösen, unter Berücksichtigung der Größe der Hash-Tabelle ist 31, die die Konstante g gleich ist. Entschuldigung, wenn ich so aussehe, aber ich frage nicht nach Code oder irgendetwas, nur ein paar Gedanken/Hinweise zu der Frage. Jeder Kommentar wird sehr geschätzt. Dank

Answer 1

Nach dem Wikipedia article on Java's string hashing algorithm (das ist der gleiche wie der Algorithmus ist es, Ihnen heute):

Wie bei jeder allgemeinen Hashing-Funktion, sind Kollisionen möglich. Für haben die Strings "FB" und "Ea" beispielsweise den gleichen Hash-Wert. Die hashCode() Umsetzung des String verwendet die Primzahl 31 und den Unterschied zwischen 'A' und 'B' ist nur 31, also die Berechnung beträgt 70 × 31 + 66 = 69 × 31 + 97.

Answer 2

Java-Strings können eine Null-Zeichen ("\0") enthalten, so dass alle die folgenden würde auf den gleichen Wert hash:

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

hier ist der Beweis (dank Eric für den ref dazu verwendet, die Hash ist):

> 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 

Ich bezweifle jedoch, dass dies die erwartete Antwort ist.

auch, wenn dies eine Prüfung wäre, bezweifle ich, dass ich mich an ASCII-Codes erinnern konnte. so ein alternativer Ansatz zur Verwendung von Sequenzen des Stils in der anderen Antwort wäre:

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

etc. (dies sind Oktal Drillinge - die oben beiden Hash bis 62). aber ist es einfach, fünf Beispiele (alle gleichen Hash) für diesen Stil zu generieren?