Encontrar colisiones en la tabla hash

Question

Estaba revisando para el examen final de las estructuras de datos, y encontré una pregunta en la final del año pasado. Después de haber trabajado en él durante las últimas tres horas, todavía no podía encontrar una manera de resolverlo, excepto por prueba y error. Aquí está la pregunta:

"Supongamos que el tamaño de la tabla hash es 31, la constante g es también de 31 años, y que se utiliza el siguiente código hash

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

y que utiliza encadenamiento separado para resolver colisiones. Enumera cinco nombres diferentes que harían hash en la misma ubicación en la tabla ".

Creo que debe haber algún tipo de trucos, posiblemente involucrando al operador del módulo, para resolver este problema, considerando que el tamaño de la tabla hash es 31, que es lo mismo que la constante g. Lo siento si sueno así, pero no estoy pidiendo código ni nada, solo algunos pensamientos/pistas sobre la pregunta. Cualquier comentario es muy apreciado. Gracias

Answer 1

Según la Wikipedia article on Java's string hashing algorithm (que es el mismo que el algoritmo que está presente):

Como con cualquier función hash en general, las colisiones son posibles. Para el ejemplo , las cadenas "FB" y "Ea" tienen el mismo valor hash. La implementación hashCode() de cadena usa el primer número 31 y la diferencia entre 'a' y 'B' es sólo 31, por lo que el cálculo es 70 × 31 + 66 = 69 × 31 + 97.

Answer 2

cadenas de Java puede contener un carácter cero ("\0"), por lo que todo el siguiente hash en el mismo valor:

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

aquí está la prueba (gracias a Eric que el árbitro siendo este el hash utilizado):

> 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 

dudo que esta sea la respuesta esperada, sin embargo.

también, si esto fuera un examen, dudo que pudiera recordar los códigos ASCII. por lo que un enfoque alternativo a la utilización de secuencias del estilo en la otra respuesta sería:

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

etc (estos son tripletes octales - lo anterior tanto de hash a 62). pero ¿es fácil generar cinco ejemplos (todos los mismos hash) para este estilo?