Un mapa de claves y valores
Este programa cuenta palabras en un Map: asocia cada clave con un valor. Por dentro, un HashMap es un arreglo de buckets. Con capacidad 16, son 16 cajones.
Este programa cuenta palabras en un Map: asocia cada clave con un valor.
Por dentro, un HashMap es un arreglo de buckets. Con capacidad 16, son 16 cajones.
Este programa cuenta palabras en un Map: asocia cada clave con un valor. Por dentro, un HashMap es un arreglo de buckets. Con capacidad 16, son 16 cajones.
put("gato", 3) no busca un lugar libre: primero le pide a la clave su hashCode().
La clave responde con un número entero: para "gato" es 3165397.
Java mezcla sus bits y aplica una máscara. El resultado es el bucket 5.
put("gato", 3) no busca un lugar libre: primero le pide a la clave su hashCode(). La clave responde con un número entero: para "gato" es 3165397. Java mezcla sus bits y aplica una máscara. El resultado es el bucket 5.
Ese número es una dirección: la clave va directo a su bucket, sin mirar los demás.
Allí se guarda la entrada completa: la clave junto con su valor.
Ese número es una dirección: la clave va directo a su bucket, sin mirar los demás. Allí se guarda la entrada completa: la clave junto con su valor.
Otra clave, otro hash: "luna" termina en el bucket 14.
Con un hash bien distribuido, las claves casi nunca comparten bucket.
Otra clave, otro hash: "luna" termina en el bucket 14. Con un hash bien distribuido, las claves casi nunca comparten bucket.
Ahora llega "mesa". Su hash es distinto al de "gato"…
…pero después de la máscara, el resultado vuelve a ser el bucket 5.
Es una colisión: dos claves distintas cayeron en el mismo bucket.
Ahora llega "mesa". Su hash es distinto al de "gato"… …pero después de la máscara, el resultado vuelve a ser el bucket 5. Es una colisión: dos claves distintas cayeron en el mismo bucket.
Dentro del bucket, equals() compara la clave nueva con la que ya estaba.
"mesa" no es igual a "gato": son claves distintas y se guardan las dos.
Dentro del bucket, equals() compara la clave nueva con la que ya estaba. "mesa" no es igual a "gato": son claves distintas y se guardan las dos.
get("mesa") repite el camino: la misma clave produce siempre el mismo hash.
En el bucket 5, equals() descarta "gato" y reconoce "mesa".
El mapa devuelve el valor asociado a esa clave: 5.
get("mesa") repite el camino: la misma clave produce siempre el mismo hash. En el bucket 5, equals() descarta "gato" y reconoce "mesa". El mapa devuelve el valor asociado a esa clave: 5.
No recorrió la colección: hizo una cuenta y fue a un solo bucket. Por eso get() es O(1).
En una List, buscar un elemento obliga a recorrerla: O(n).
hashCode() elige el cajón; equals() elige el elemento dentro del cajón.
No recorrió la colección: hizo una cuenta y fue a un solo bucket. Por eso get() es O(1). En una List, buscar un elemento obliga a recorrerla: O(n). hashCode() elige el cajón; equals() elige el elemento dentro del cajón.