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 ...