Trovare collisioni nella tabella hash

Question

Stavo esaminando l'esame finale delle mie strutture dati e mi sono imbattuto in una domanda nella finale dell'anno scorso. Avendo lavorato su di esso nelle ultime tre ore, non riuscivo ancora a trovare un modo per risolverlo, se non per tentativi ed errori. Ecco la domanda:

"Supponiamo che la dimensione della tabella hash è 31, la costante g è anche 31, e di utilizzare il seguente codice hash

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

e di utilizzare concatenazioni separate per risolvere collisioni: elenca cinque nomi diversi che vorrebbero l'hash nella stessa posizione nella tabella. "

Penso che ci debba essere una sorta di trucchi, possibilmente coinvolgendo l'operatore modulo, per risolvere questo problema, considerando che la dimensione della tabella hash è 31, che è la stessa della costante g. Scusa se ti sembra così, ma non chiedo codice o altro, solo alcuni pensieri/suggerimenti sulla domanda. Ogni commento è molto apprezzato. Grazie

Answer 1

Secondo la Wikipedia article on Java's string hashing algorithm (che è lo stesso come algoritmo si presenti):

Come con qualsiasi funzione di hashing generale, le collisioni sono possibili. Per esempio , le stringhe "FB" e "Ea" hanno lo stesso valore di hash. L'implementazione hashCode() della stringa utilizza il numero primo 31 e la differenza tra 'a' e 'B' è solo 31, quindi il calcolo è 70 × 31 + 66 = 69 × 31 + 97.

Answer 2

stringhe Java può contenere un carattere zero ("\0"), in modo che tutti i seguenti avrebbero hash allo stesso valore:

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

ecco la prova (grazie a Eric per l'arbitro a questo essere l'hash utilizzato):

> 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 

dubito che questa sia la risposta attesa, però.

Inoltre, se questo fosse un esame, dubito che potessi ricordare i codici ASCII. così un approccio alternativo all'uso di sequenze dello stile in altra risposta sarebbe:

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

etc (questi sono triplette ottale - quanto sopra sia hash a 62). ma è facile generare cinque esempi (tutti gli stessi hash) per questo stile?