sirve - Consistencia de hashCode() en una cadena de Java

java hashcode vulnerability

Question

El valor de hashCode de una cadena Java se calcula como ( String.hashCode() ):

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

¿Hay alguna circunstancia (por ejemplo, versión de JVM, proveedor, etc.) en la que la siguiente expresión se evalúe como falsa?

boolean expression = "This is a Java string".hashCode() == 586653468

Actualización n. ° 1: si afirma que la respuesta es "sí, existen tales circunstancias", entonces proporcione un ejemplo concreto de cuándo "Esto es una cadena Java" .hashCode ()! = 586653468. Intente ser tan específico / concreto como sea posible.

Actualización n. ° 2: todos sabemos que confiar en los detalles de implementación de hashCode () es malo en general. Sin embargo, estoy hablando específicamente de String.hashCode (), así que por favor, mantengan la respuesta enfocada a String.hashCode (). Object.hashCode () es totalmente irrelevante en el contexto de esta pregunta.

Answer 1

Como se dijo anteriormente, en general no debe confiar en que el código hash de una clase permanezca igual. Tenga en cuenta que incluso las ejecuciones posteriores de la misma aplicación en la misma VM pueden producir diferentes valores hash. AFAIK the Sun La función hash de JVM calcula el mismo hash en cada ejecución, pero eso no está garantizado.

Tenga en cuenta que esto no es teórico. La función hash para java.lang.String se modificó en JDK1.2 (el hash antiguo tenía problemas con cadenas jerárquicas como URL o nombres de archivos, ya que tendía a producir el mismo hash para cadenas que solo diferían al final).

java.lang.String es un caso especial, ya que el algoritmo de su hashCode () está (ahora) documentado, por lo que probablemente pueda confiar en eso. Todavía consideraría que es una mala práctica. Si necesita un algoritmo hash con propiedades especiales documentadas, simplemente escriba uno :-).

Answer 2

Encontré algo sobre JDK 1.0 y 1.1 y> = 1.2:

En JDK 1.0.x y 1.1.x, la función hashCode para cadenas largas funcionó al muestrear cada enésimo carácter. Esto garantizaba bastante que tendrías muchas secuencias de hash con el mismo valor, lo que ralentizaría la búsqueda de Hashtable. En JDK 1.2, la función se ha mejorado para multiplicar el resultado hasta el momento por 31 y luego agregar el siguiente carácter en secuencia. Esto es un poco más lento, pero es mucho mejor para evitar colisiones. Fuente: http://mindprod.com/jgloss/hashcode.html

Algo diferente, porque parece que necesita un número: ¿qué le parece usar CRC32 o MD5 en lugar de hashcode y está listo para empezar? Sin discusiones ni preocupaciones ...

Answer 3

No debe confiar en que un código hash sea igual a un valor específico. Solo que devolverá resultados consistentes dentro de la misma ejecución. Los documentos API dicen lo siguiente:

El contrato general de hashCode es:

• Cada vez que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación Java, el método hashCode debe devolver el mismo entero de forma consistente, siempre que no se modifique la información utilizada en comparaciones iguales en el objeto. Este entero no necesita ser consistente desde una ejecución de una aplicación hasta otra ejecución de la misma aplicación.

EDITAR Dado que javadoc para String.hashCode () especifica cómo se calcula el código hash de una cadena, cualquier violación de esto violaría la especificación API pública.

Answer 4

Otro (!) Tema de qué preocuparse es el posible cambio de implementación entre versiones tempranas / tardías de Java. No creo que los detalles de la implementación sean inamovibles, por lo que una posible actualización a una futura versión de Java podría causar problemas.

En hashCode() , no confiaría en la implementación de hashCode() .

Quizás pueda resaltar qué problema está tratando de resolver utilizando este mecanismo, y eso resaltará un enfoque más adecuado.

Answer 5

Puedo ver esa documentación desde Java 1.2.

Si bien es cierto que, en general, no debes confiar en que la implementación de un código hash siga siendo la misma, ahora se ha documentado el comportamiento de java.lang.String , por lo que cambiarlo se consideraría como una ruptura de los contratos existentes.

Siempre que sea posible, no debe confiar en que los códigos hash se mantengan iguales en todas las versiones, etc., pero en mi opinión java.lang.String es un caso especial simplemente porque el algoritmo ha sido especificado ... siempre y cuando esté dispuesto a abandonar compatibilidad con las versiones antes de que se especificara el algoritmo, por supuesto.

Answer 6

Si le preocupan los cambios y posiblemente las máquinas virtuales incompatibles, simplemente copie la implementación de código hash existente en su propia clase de utilidad y utilícela para generar sus códigos hash.

Answer 7

Solo para responder a su pregunta y no continuar ninguna discusión. La implementación de Apache Harmony JDK parece usar un algoritmo diferente, al menos se ve totalmente diferente:

Sun JDK

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Armonía Apache

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

No dude en comprobarlo usted mismo ...