java - sobreescribir - ¿Por qué el método equals en String no usa hash?

metodo hash java

Question

El código del método equals en la clase String es

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}

Tengo una pregunta: ¿por qué este método no usa hashCode ()?

Que yo sepa, hashCode () puede comparar dos cadenas rápidamente.

ACTUALIZACIÓN: Sé que dos cadenas desiguales, pueden tener los mismos hashes. Pero dos cadenas iguales tienen hashes iguales. Por lo tanto, al usar hashCode (), podemos ver inmediatamente que dos cadenas son desiguales.

Simplemente estoy pensando que usar hashCode () puede ser un buen filtro entre equals .

ACTUALIZACIÓN 2: Aquí un código, de lo que estamos hablando aquí.

Es un ejemplo de cómo el método de cadena es igual a

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        if (hashCode() == anotherString.hashCode()){
            int n = count;
            if (n == anotherString.count) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = offset;
                int j = anotherString.offset;
                while (n-- != 0) {
                    if (v1[i++] != v2[j++])
                        return false;
                }
                return true;
            }
        }else{
            return false;
        }
    }
    return false;
}

Answer 1

Como creo, hashCode () puede hacer que la comparación de dos cadenas sea más rápida.

Argumentos?

Argumentos en contra de esta propuesta:

• Más operaciones

hashcode() de String tiene que acceder a todos los caracteres de la cadena y tiene que hacer 2 cálculos para cada carácter.
Así que necesitamos una cadena con n caracteres 5*n operaciones (carga, multiplicación, búsqueda / carga, multiplicación, almacenamiento). Dos veces, porque comparamos dos cuerdas. (Ok, una tienda y una carga realmente no cuentan en una implementación razonable).
Para el mejor de los casos, esto hace un total de 10*x operaciones para dos cadenas con longitud m y n y x=min(m,n) . El peor caso es 10*x con x=m=n . Promedio en algún lugar entre, quizás (m*n)/2 .

Las necesidades actuales de implementación son iguales en las mejores operaciones de caso 3 . 2 cargas, 1 comparar. Lo peor es 3*x operaciones para dos cadenas con longitud m y n y x=m=n . El promedio está en algún lugar entre, quizás 3*(m*n)/2 .

• Incluso si almacenamos en caché el hash, no está claro si guardamos algo

Tenemos que analizar los patrones de uso. Puede ser que la mayoría de las veces, solo pidamos una vez entre iguales, no varias veces. Incluso si preguntamos varias veces, no podría ser suficiente ahorrar tiempo con el almacenamiento en caché.

No es directo contra la velocidad, pero sigue siendo un buen contra argumento:

• Contador intuitivo

No esperamos un código hash(a)==hash(b) en iguales, porque sabemos con certeza que hash(a)==hash(b) para algunos a!=b Todos los que lean esto (y el conocimiento sobre el hash) se preguntarán qué está sucediendo allí.

• Conduce a malos ejemplos / comportamiento inesperado

Ya puedo ver la siguiente pregunta en SO: "Tengo una cadena con miles de millones de veces ''a''. ¿Por qué se tarda una eternidad en compararla con igual () contra ''b''?" :)

Answer 2

1) El cálculo del código hash puede no ser más rápido que comparar directamente las cadenas.

2) si el código hash es igual, las cadenas pueden no ser iguales

Answer 3

AFAIK, la siguiente verificación podría agregarse a String. Esto comprueba que si los códigos hash están establecidos y son diferentes, entonces las cadenas no pueden ser iguales.

if (hash != 0 && anotherString.hash != 0 && hash != anotherString.hash)
    return false;
if (hash32 != 0 && anotherString.hash32 != 0 && hash32 != anotherString.hash32)
    return false;

Answer 4

Esta pregunta realmente ha sido considerada por los desarrolladores del JDK. No pude encontrar en los diversos mensajes por qué no se ha incluido. La mejora también se enumera en la base de datos de errores .

A saber, uno de los cambios propuestos es:

public boolean equals(Object anObject) {
    if (this == anObject) // 1st check identitiy
        return true;
    if (anObject instanceof String) { // 2nd check type
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) { // 3rd check lengths
            if (n != 0) { // 4th avoid loading registers from members if length == 0
                int h1 = hash, h2 = anotherString.hash;
                if (h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
                    return false;

También hubo una discusión para usar == para cadenas internadas (es decir, si ambas cadenas están internadas: if (this != anotherString) return false; ).

Answer 5

Esto puede ser una buena idea para muchos casos de uso.

Sin embargo, como una clase básica que se usa ampliamente en todo tipo de aplicaciones, el autor realmente no tiene idea de si esta comprobación adicional puede salvar o perjudicar el rendimiento en promedio.

Voy a suponer que la mayoría de String.equals() se invocan en un Hashmap, una vez que se sabe que los códigos hash son iguales, por lo que volver a probar los códigos hash no tiene sentido.

Si consideramos la posibilidad de comparar 2 cadenas aleatorias, incluso con un conjunto de caracteres pequeños como el ASCII de EE. UU., Es muy probable que los hashes sean diferentes, y la comparación de carácter por carácter falla en la primera característica. Así que será un desperdicio revisar los hashes.

Answer 6

Hashcode podría ser un control de primera ronda para la desigualdad. Sin embargo, presenta algunas compensaciones.

1. String hashcodes de String se calculan de manera perezosa, aunque utilizan un valor de "guarda". Si está comparando cadenas con largas vidas (es decir, es probable que hayan tenido el código hash computado), esto no es un problema. De lo contrario, no podrá calcular el código hash (potencialmente costoso) o ignorar la verificación cuando el código hash todavía no se haya calculado. Si tiene muchas cadenas de corta duración, ignorará la verificación con más frecuencia de la que usará.
2. En el mundo real, la mayoría de las cadenas difieren en sus primeros caracteres, por lo que no ahorrará mucho al verificar primero el código hash. Hay, por supuesto, excepciones (como las URL), pero nuevamente, en la programación del mundo real ocurren con poca frecuencia.

Answer 7

La cadena de código hash no está disponible de forma gratuita y automática. Para poder confiar en el código hash, se debe calcular para ambas cadenas y solo así se puede comparar. Como las colisiones son posibles, la segunda comparación de caracteres es necesaria si los códigos hash son iguales.

Mientras que String aparece como inmutable para el programador habitual, tiene el campo privado para almacenar su código hash una vez que se calcula. Sin embargo, este campo solo se calcula cuando primero se requiere el código hash. Como puedes ver en el código fuente de String here :

 private int hash;

 public int hashCode() {
      int h = hash;
      if (h == 0) {
         ...
         hash = h;  
      }
      return h;
 }

Por lo tanto, no es obvio que tenga sentido calcular primero el código hash. Para su caso específico (tal vez las mismas instancias de cadenas realmente largas se comparan entre sí muchas veces), todavía puede ser: perfil.

Answer 8

Si el código hash tiene en cuenta todo el contenido de la cadena, el cálculo del código hash de una cadena con n caracteres toma n operaciones. Para cuerdas largas eso es mucho. La comparación de dos cadenas toma n operaciones si son iguales, no más que el cálculo del hash. Pero si las cadenas son diferentes, entonces es probable que se encuentre una diferencia mucho antes.

Las funciones de hash de cadena generalmente no consideran a todos los caracteres para cadenas muy largas. En ese caso, si comparo dos cadenas, primero podría comparar los caracteres utilizados por la función hash, y soy al menos tan rápido como revisar los hashes. Pero si no hay diferencia en estos caracteres, entonces el valor de hash será el mismo, así que tengo que comparar las cadenas completas de todos modos.

Resumen: una buena comparación de cadenas nunca es más lenta, pero a menudo es mucho más rápida que comparar los hashes (y comparar las cadenas cuando coinciden).