tipos - tablas hash en java

¿Puede una cadena no vacía tener un código hash de cero?

Question

Por "no vacío", quiero decir en esta pregunta una cadena que contiene al menos un carácter distinto de cero.

Para referencia, aquí está la implementación de hashCode :

1493 public int hashCode() {
1494 int h = hash;
1495 if (h == 0) {
1496 int off = offset;
1497 char val[] = value;
1498 int len = count;
1499
1500 for (int i = 0; i < len; i++) {
1501 h = 31*h + val[off++];
1502 }
1503 hash = h;
1504 }
1505 return h;
1506 }

y el algoritmo se especifica en la documentación.

Antes de que ocurra un desbordamiento de enteros, la respuesta es fácil: es no. Pero lo que me gustaría saber es si, debido al desbordamiento de enteros, ¿es posible que una cadena no vacía tenga un código hash de cero? ¿Puedes construir uno?

Lo que estoy buscando sería idealmente una demostración matemática (o un enlace a uno) o un algoritmo de construcción.

Answer 1

Por supuesto. La cadena f5a5a608, por ejemplo, tiene un código hash de cero.

Encontré que a través de una simple búsqueda de fuerza bruta:

public static void main(String[] args){
long i = 0;
loop: while(true){
String s = Long.toHexString(i);
if(s.hashCode() == 0){
System.out.println("Found: ''"+s+"''");
break loop;
}
if(i % 1000000==0){
System.out.println("checked: "+i);
}
i++;
}
}

Edición: Joseph Darcy, quien trabajó en la JVM, incluso escribió un programa que puede construir una cadena con un código hash dado (para probar la implementación de cadenas en las instrucciones switch / case) básicamente ejecutando el algoritmo hash a la inversa.

Answer 2

solo ten cuidado de eso int h; . Puede desbordarse, cada cadena que satisface h % 2^31 == 0 puede llevar a esto.

public class HelloWorld {
public static void main(String []args) {
System.out.println("/u0001!qbygvW".hashCode());
System.out.println("9 $Ql(0".hashCode());
System.out.println(" #t(}lrl".hashCode());
System.out.println(" !!#jbw}a".hashCode());
System.out.println(" !!#jbw|||".hashCode());
System.out.println(" !!!!Se|aaJ".hashCode());
System.out.println(" !!!!/"xurlls".hashCode());
}
}

Un montón de cuerdas ...