Probando la igualdad de cadenas usando hashCode()

Question

¿Hay alguna razón por la cual una cadena Java no pueda ser probada para la igualdad usando su método hashCode? Así que, básicamente, en lugar de ....

"hello".equals("hello") 

Usted podría utilizar ...

"hello".hashCode() == "hello".hashCode() 

Esto sería útil porque una vez que una cadena se ha calculado que es código hash a continuación la comparación de una cadena sería tan eficiente como comparar un int como la cadena almacena en caché el hashcode y es bastante probable que la cadena esté en el grupo de cadenas de todos modos, si lo diseñó de esa manera.

Answer 1

porque: los hashCodes de dos objetos deben ser iguales si los objetos son iguales; sin embargo, si dos objetos son desiguales, el código hash aún puede ser igual.

(modificado según comentario)

Answer 2

El valor hashCode no es único, lo que significa que las cadenas no puede llegar a igualar. Para mejorar el rendimiento, a menudo las implementaciones de iguales realizarán una comprobación de hashCode antes de realizar comprobaciones más laboriosas.

Answer 3

No hay ninguna razón para no usar hashCode como usted lo describe.

Sin embargo, debe tener en cuenta las colisiones. Existe la posibilidad, una pequeña posibilidad, de que dos cadenas diferentes hagan hash con el mismo valor. Considera hacer un hashCode al principio, y si es igual también haz la comparación completa usando los iguales().

Answer 4

Razón muy simple: riesgo de colisiones ... Un código hash tendrá valores mucho menos posibles que una cadena. Depende del tipo de hash que genere, pero tomemos un ejemplo muy simple, donde se agregarían los valores ordinales de las letras, multiplicados por su posición: a = 1, b = 2, etc. Por lo tanto, 'hola' haría traducir a: h: 8x1 = 8, e: 5x2 = 10, l: 12x3 = 36, l: 12x4 = 48, o: 15x5 = 75. 8 + 10 + 36 + 48 + 75 = 177.

¿Hay otros valores de cadena que podrían terminar en 177 hash? ¡Por supuesto! Un montón de opciones Siéntase libre de calcular algunos.

Aún así, este método hash utiliza un método simple. Java y .NET utilizan un algoritmo de hash más complejo con muchas menos posibilidades de tales colisiones. Pero aún así, existe la posibilidad de que dos cadenas diferentes den como resultado el mismo valor hash, por lo que este método es menos confiable.

Answer 5

Déjame darte un ejemplo de contador. Prueba de esto,

public static void main(String[] args) { 
    String str1 = "0-42L"; 
    String str2 = "0-43-"; 

    System.out.println("String equality: " + str1.equals(str2)); 
    System.out.println("HashCode eqauality: " + (str1.hashCode() == str2.hashCode())); 
} 

El resultado en mi Java,

String equality: false 
HashCode eqauality: true 

Answer 6

Usted puede conseguir el efecto deseado con String.intern() (que se implementa utilizando una tabla hash.)

Se puede comparar el devuelva los valores de intern() usando el operador ==. Si se refieren a la misma cadena, las cadenas originales eran equivalentes (es decir, equals() habrían devuelto true), y solo requiere una comparación de puntero (que tiene el mismo costo que una comparación int).)

String a = "Hello"; 
String b = "Hel" + "lo"; 

System.out.println(a.equals(b)); 
System.out.println(a == b); 

String a2 = a.intern(); 
String b2 = b.intern(); 

System.out.println(a2.equals(b2)); 
System.out.println(a2 == b2); 

Salida:

true 
false 
true 
true 

Answer 7

como muchos dijeron hashCode no lo hace singularidad de garantía. de hecho, no puede hacer eso por una razón muy simple.

hashCode devuelve un int, lo que significa que hay 2^32 valores posibles (alrededor de 4.000,000,000), pero seguramente hay más de 2^32 cadenas posibles, lo que significa que al menos dos cadenas tienen el mismo valor de código hash.

esto se llama Pigeonhole principle.

Answer 8

Otros han señalado por qué no funcionará. Así que solo agregaré el apéndice de que la ganancia sería mínima de todos modos.

Cuando compara dos cadenas en Java, la función String equals comprueba primero si son dos referencias al mismo objeto. Si es así, inmediatamente devuelve verdadero. Luego verifica si las longitudes son iguales. Si no, devuelve falso. Solo entonces comienza a comparar personaje por personaje.

Si está manipulando datos en la memoria, la comparación del mismo objeto puede manejar rápidamente el "mismo" caso, y eso es una comparación rápida, umm, de 4 bytes, creo. (Alguien me corrige si tengo la longitud de un objeto manejar mal.)

Para la mayoría de las cuerdas desiguales, apostaría a que la longitud de comparar rápidamente los encuentra no iguales. Si compara dos nombres de cosas (clientes, ciudades, productos, lo que sea), generalmente tendrán una duración desigual. Por lo tanto, una comparación simple simple los descarta rápidamente.

El peor caso para el rendimiento va a ser dos largas, idénticas, pero no las mismas cadenas de objetos. Luego tiene que hacer el objeto manejar comparar, falso, seguir comprobando. La duración se compara, es verdad, sigue comprobando. Luego, carácter por personaje a través de toda la longitud de la cadena para verificar que sí, de hecho, son iguales hasta el final.

Answer 9

Dos cadenas diferentes pueden generar fácilmente el mismo código hash o diferentes códigos hash. Si quiere una prueba de igualdad, el código hash no dará un resultado único. Cuando usamos la clase String devolverá un valor diferente de código hash. Así que la clase String buffer debería aplicarse para tener el mismo código hash para cada objeto concatenado.