java - example - ¿Mala idea usar la tecla String en HashMap?

map java example

Question

Entiendo que el método hashCode() la clase String no está garantizado para generar códigos hash únicos para String-s distintas. Veo mucho uso de poner claves String en HashMap-s (usando el método predeterminado String hashCode ()). Gran parte de este uso podría ocasionar importantes problemas de aplicación si un mapa put desplazara una entrada HashMap que previamente se colocó en el mapa con una clave String verdaderamente distinta.

¿Cuáles son las probabilidades de que se ejecute en el escenario donde String.hashCode () devuelve el mismo valor para String-s distintas? ¿Cómo trabajan los desarrolladores en torno a este problema cuando la clave es un String?

Answer 1

Estás hablando de colisiones hash. Las colisiones hash son un problema, independientemente del tipo que se tenga hashCode''d. Todas las clases que usan hashCode (p. Ej. HashMap) manejan las colisiones hash muy bien. Por ejemplo, HashMap puede almacenar múltiples objetos por cubo.

No se preocupe, a menos que llame a hashCode usted mismo. Las colisiones hash, aunque raras, no rompen nada.

Answer 2

Esto no es un problema, es solo cómo funcionan las tablas. Es probablemente imposible tener códigos hash distintivos para todas las cadenas distintas, porque hay cadenas mucho más distintas que los enteros.

Como otros han escrito, las colisiones hash se resuelven mediante el método equals (). El único problema que esto puede causar es la degeneración de la tabla hash, lo que conduce a un mal rendimiento. Es por eso que el HashMap de Java tiene un factor de carga , una relación entre cubos y elementos insertados que, cuando se supera, provocará un reajuste de la tabla con el doble de cubetas.

En general, esto funciona muy bien, pero solo si la función hash es buena, es decir, no genera más que el número de colisiones esperadas estadísticamente para su conjunto de entrada particular. String.hashCode() es bueno en este sentido, pero esto no siempre fue así. Allegedly , antes de Java 1.2 solo incluía cada n-ésimo personaje. Esto fue más rápido, pero causó colisiones predecibles para todos los String que compartían cada n-ésimo personaje, muy malo si no estás lo suficientemente tranquilo como para tener una entrada tan regular, o si alguien quiere hacer un ataque de DOS en tu aplicación.

Answer 3

Sospecho fuertemente que el método HashMap.put no determina si la clave es la misma con solo mirar String.hashCode .

Definitivamente va a haber una posibilidad de una colisión hash , por lo que uno esperaría que también se llame al método String.equals para asegurarse de que las String son realmente iguales, si de hecho hay un caso donde las dos String tienen el mismo valor devuelto por hashCode .

Por lo tanto, la nueva clave String solo se consideraría como la misma clave String que una que ya está en HashMap si y solo si el valor devuelto por String.hashCode es igual, y el método String.equals devuelve true .

También para agregar, este pensamiento también sería cierto para las clases que no sean String , ya que la clase Object ya tiene el hashCode y equals métodos.

Editar

Entonces, para responder la pregunta, no, no sería una mala idea usar una String para una clave de un HashMap .

Answer 4

Te dirijo a la respuesta here . Si bien no es una mala idea usar cadenas (@CPerkins explicó por qué, perfectamente), almacenar los valores en un hashmap con claves enteras es mejor , ya que generalmente es quicker (aunque imperceptible) y tiene menos posibilidades (en realidad, no hay posibilidad) de colisiones

Vea este cuadro de colisiones usando 216553 claves en cada caso, (robado de esta here , reformateado para nuestra discusión)

Hash           Lowercase      Random UUID  Numbers 
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis*
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis***
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis***
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis

Avg Time per key    0.8ps       2.5ps         0.44ps
Collisions (%)      0.002%      0.002%         0%

Por supuesto, el número de enteros está limitado a 2 ^ 32, donde no hay límite para el número de cadenas (y no existe un límite teórico para la cantidad de claves que se pueden almacenar en un HashMap ). Si utiliza un float long (o incluso float ), las colisiones serán inevitables y, por lo tanto, no serán "mejores" que una cuerda. Sin embargo, incluso a pesar de las colisiones hash, put() y get() siempre pondrán / obtendrán el par clave-valor correcto (ver la edición a continuación).

Al final, realmente no importa, así que usa lo que sea más conveniente. Pero si la conveniencia no hace diferencia, y no tiene la intención de tener más de 2 ^ 32 entradas, le sugiero que use ints como claves.

EDITAR

Mientras que lo anterior es definitivamente cierto, NUNCA utilice "StringKey" .hashCode () para generar una clave en lugar de la clave de String original por razones de rendimiento: 2 cadenas diferentes pueden tener el mismo código hash, lo que provoca la sobreescritura en su método put() . La implementación de Java de HashMap es lo suficientemente inteligente como para manejar cadenas (cualquier tipo de clave, en realidad) con el mismo código hash automáticamente, por lo que es conveniente dejar que Java maneje estas cosas por usted.

Answer 5

Los desarrolladores no tienen que solucionar el problema de las colisiones hash en HashMap para lograr la corrección del programa.

Hay un par de cosas clave para entender aquí:

1. Las colisiones son una característica inherente del hashing, y tienen que serlo. El número de valores posibles (Cadenas en su caso, pero también se aplica a otros tipos) es mucho mayor que el rango de los enteros.
2. Cada uso de hashing tiene una forma de manejar las colisiones, y las colecciones de Java (incluido HashMap) no son una excepción.
3. Hashing no está involucrado en pruebas de igualdad. Es cierto que los objetos iguales deben tener hashcodes iguales, pero lo contrario no es cierto: muchos valores tendrán el mismo código hash. Por lo tanto, no intente utilizar una comparación de código hash como sustituto de la igualdad. Las colecciones no. Usan hashing para seleccionar una subcolección (llamada un cubo en el mundo de Java Collections), pero usan .equals () para verificar realmente la igualdad.
4. No solo no tiene que preocuparse por las colisiones que causan resultados incorrectos en una colección, sino que para la mayoría de las aplicaciones, también * por lo general * no tiene que preocuparse por el rendimiento: las colecciones hash de Java hacen un muy buen trabajo al administrar hashcodes.
5. Mejor aún, para el caso que usted preguntó acerca de (Cadenas como claves), ni siquiera tiene que preocuparse por los propios códigos hash, porque la clase String de Java genera un código hash bastante bueno. Lo mismo ocurre con la mayoría de las clases de Java suministradas.

Algunos detalles más, si lo desea:

La forma en que funciona el hash (en particular, en el caso de colecciones hash como HashMap de Java, que es lo que preguntaste) es esto:

• HashMap almacena los valores que le da en una colección de subcolecciones, llamadas cubetas. Estos se implementan en realidad como listas vinculadas. Hay un número limitado de estos: iirc, 16 para comenzar de forma predeterminada, y el número aumenta a medida que agrega más elementos al mapa. Siempre debe haber más cubos que valores. Para dar un ejemplo, usando los valores predeterminados, si agrega 100 entradas a un HashMap, habrá 256 segmentos.

• Cada valor que se puede usar como clave en un mapa debe ser capaz de generar un valor entero, llamado código hash.

• HashMap usa este código hash para seleccionar un cubo. En última instancia, esto significa tomar el modulo valores enteros del número de cubos, pero antes de eso, HashMap de Java tiene un método interno (llamado hash() ), que modifica el código hash() para reducir algunas fuentes conocidas de aglutinación.

• Al buscar un valor, HashMap selecciona el cubo y luego busca el elemento individual mediante una búsqueda lineal de la lista vinculada, utilizando .equals() .

Por lo tanto, no es necesario evitar las colisiones para la corrección, y generalmente no tiene que preocuparse por el rendimiento, y si usa clases nativas de Java (como String), no tiene que preocuparse por ellas. generando los valores de hashcode cualquiera.

En el caso de que tenga que escribir su propio método de código hash (lo que significa que ha escrito una clase con un valor compuesto, como un par de nombre / apellido), las cosas se complican un poco. Es bastante posible equivocarse aquí, pero no es ciencia espacial. Primero, debes saber esto: lo único que debes hacer para garantizar la corrección es asegurarte de que objetos iguales produzcan códigos hash iguales. Entonces, si escribe un método hashcode () para su clase, también debe escribir un método equals (), y debe examinar los mismos valores en cada uno.

Es posible escribir un método hashcode () que es malo pero correcto, con lo que quiero decir que satisfaría la restricción de "objetos iguales deben producir códigos equivalentes", pero aún tiene un rendimiento muy bajo al tener muchas colisiones.

El peor caso canónico degenerado de esto sería escribir un método que simplemente devuelva un valor constante (por ejemplo, 3) para todos los casos. Esto significaría que cada valor se dividiría en hash en el mismo cubo.

Todavía funcionaría , pero el rendimiento se degradaría al de una lista vinculada.

Obviamente, no escribirás un método hashcode () tan terrible. Si está usando un IDE decente, es capaz de generar uno para usted. Como ama el código, aquí está el código para la clase firstname / lastname anterior.

public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}