Códigos hash y funciones hash

En resumen: Un código hash es un número que se calcula a partir de una clave con hashCode(); HashMap lo usa para elegir la cubeta donde buscar, así que encuentra una clave rápido incluso entre un millón.

Problema

El asiento se vendió dos veces

La taquilla del teatro guarda los asientos vendidos en un diccionario: asiento → nombre del cliente. Un asiento es una clase con una fila y un número:

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }
}

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "María");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Iván");
System.out.println(bookings.size());

Salida

null
1
2

María compró el asiento 5/12, pero get con el mismo asiento devuelve null. Después Iván compra el mismo asiento, y el diccionario ahora tiene dos claves 5/12. ¿Por qué?

La idea

Código hash: un número a partir de la clave

Un HashMap no compara la clave con todas las demás. Calcula un número entero a partir de la clave, y con él sabe dónde buscar. Ese número se llama código hash, y lo devuelve el método hashCode(). Todo objeto lo tiene, porque está en Object.

System.out.println("María".hashCode());
System.out.println("María".hashCode());
System.out.println("Mario".hashCode());
System.out.println("maría".hashCode());

Salida

74117842
74117842
74113764
103670514

• El mismo texto da el mismo número, siempre y en cualquier computadora.
• Un cambio pequeño da otro número: "María", "Mario" y "maría" son tres códigos hash distintos.
• Un código hash se calcula rápido, sin importar cuántas claves haya en el diccionario.

El método que produce el número se llama función hash.

Más precisamente, para curiosos

• Para String, la fórmula está definida en la documentación de Java: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], donde s[i] es el código de cada carácter. El resultado es un int, así que al desbordarse se vuelve negativo.

• Las funciones hash criptográficas, como SHA-256, son otra cosa. Dan un resultado largo, y en la práctica es imposible encontrar dos textos con el mismo hash. Por eso se usan para comprobar que un archivo no fue alterado y para guardar contraseñas. hashCode() sirve para búsquedas rápidas y no da esa protección.

Míralo

Las cubetas

Por dentro, un HashMap es un array de cubetas. El número de cubeta de una clave es el resto de dividir el hash entre el número de cubetas:

String[] keys = { "Clara", "Luis", "Iván", "Rosa" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> cubeta " + index);
}

Paso a paso, en palabras

1. Cuatro claves y ocho cubetas vacías, numeradas del 0 al 7.
2. "Clara".hashCode() es 65190183. El resto de dividir entre 8 es 7: esa es la cubeta.
3. "Luis" da 2379923, cubeta 3.
4. "Iván" da 2295226, cubeta 2.
5. "Rosa" también cae en la cubeta 3: una colisión. Las dos claves están en una misma cubeta: "Rosa" cuelga detrás de "Luis" como una cadena.
6. Se busca "Rosa": el mismo número, la misma cubeta 3. equals con "Luis": no. Con "Rosa": sí.

• put calcula la cubeta y guarda ahí el par. get calcula la misma cubeta y busca solo en ella. Por eso es rápido incluso con un millón de claves.
• Math.floorMod es un resto de la división que nunca es negativo. Un código hash puede ser negativo, pero un número de cubeta no.
• "Luis" y "Rosa" cayeron en la cubeta 3. Esto se llama colisión. De eso trata la siguiente tarjeta.

Más precisamente, para curiosos

• El HashMap real calcula el índice de forma un poco distinta: (h ^ (h >>> 16)) & (n - 1). El número de cubetas n siempre es una potencia de dos, y & (n - 1) es un resto rápido de la división entre n. Por eso allí los números son otros, pero el principio es el mismo.

Pruébalo

¿Qué cubeta?

El código hash de un Integer es el propio número. Los números de pedido van a un diccionario con 4 cubetas.

¿Qué imprimirá el programa?

int[] orderIds = { 6, 10, 13, 21 };
for (int id : orderIds) {
    Integer key = id;
    System.out.println(id + " -> cubeta " + Math.floorMod(key.hashCode(), 4));
}

Respuesta

6 -> cubeta 2
10 -> cubeta 2
13 -> cubeta 1
21 -> cubeta 1

6 -> cubeta 2
10 -> cubeta 0
13 -> cubeta 1
21 -> cubeta 3

6 -> cubeta 1
10 -> cubeta 2
13 -> cubeta 3
21 -> cubeta 4

6 -> cubeta 6
10 -> cubeta 10
13 -> cubeta 13
21 -> cubeta 21

Comprobar

La idea

Colisión: hashCode encuentra la cubeta, equals encuentra la clave

Claves distintas pueden tener el mismo código hash. Los dos ejemplos más conocidos:

System.out.println("Aa".hashCode() + " " + "BB".hashCode());

Map<String, Integer> codes = new HashMap<>();
codes.put("Aa", 1);
codes.put("BB", 2);
System.out.println(codes.get("Aa") + " " + codes.get("BB"));

Salida

2112 2112
1 2

Las dos claves están en una misma cubeta, pero el diccionario no las confunde. La cubeta guarda una pequeña lista enlazada de pares. get la recorre y compara con equals hasta encontrar la clave.

Así que los dos pasos funcionan así:

1. hashCode() dice en qué cubeta buscar.
2. equals() dice cuál de las claves de la cubeta es la que buscas.

Ahora queda claro qué pasó con el asiento del teatro. Seat no sobrescribe ninguno de los dos, así que usa las versiones de Object. Ahí, equals es ==, y hashCode suele ser distinto para cada objeto. Los dos objetos new Seat(5, 12) son dos objetos distintos, así que también son dos claves distintas.

La idea

El contrato: equals y hashCode juntos

Seat tiene que decir cuándo dos asientos son el mismo asiento, y dar a asientos iguales el mismo código hash:

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Seat)) {
            return false;
        }
        Seat s = (Seat) other;
        return row == s.row && number == s.number;
    }

    @Override
    public int hashCode() {
        return 31 * row + number;
    }
}

Con el mismo código en main que en la primera tarjeta:

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "María");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Iván");
System.out.println(bookings.size());

Salida

María
1
1

Las reglas que espera Java:

• Si a.equals(b), entonces a.hashCode() == b.hashCode(). Siempre.
• Si los códigos hash son iguales, los objetos pueden ser distintos. Eso es una colisión.
• Si sobrescribes equals, sobrescribe también hashCode, con los mismos campos.

Más precisamente, para curiosos

• ¿Por qué 31? Es un número primo impar, y mezcla bien. Multiplicar por 31 hace que el hash dependa del orden: el asiento 5/12 y el asiento 12/5 tienen códigos hash distintos. Con row + number, los dos caerían en la misma cubeta.
• En lugar de la fórmula, puedes escribir Objects.hash de java.util.Objects. Calcula lo mismo a partir de los campos que le das:

@Override
public int hashCode() {
    return Objects.hash(row, number);
}

• equals recibe un Object, así que primero comprueba con instanceof si el otro es siquiera un Seat, y después lo convierte. Es la conversión hacia abajo del módulo «Herencia y polimorfismo».

Pruébalo

Encuentra el error

El catálogo guarda los productos en un HashSet. Dos productos con el mismo código son el mismo producto, aunque el precio haya cambiado. Pero contains con el precio nuevo devuelve false:

Set<Product> catalog = new HashSet<>();
catalog.add(new Product("A-100", 25.0));
// El precio bajó, pero es el mismo producto.
System.out.println(catalog.contains(new Product("A-100", 19.9)));

Salida

false

¿En qué línea de la clase está el error?

Elige la línea con el error.

1class Product {2 String code;3 double price;45 Product(String code, double price) {6 this.code = code;7 this.price = price;8 }910 @Override11 public boolean equals(Object other) {12 if (!(other instanceof Product)) {13 return false;14 }15 return code.equals(((Product) other).code);16 }1718 @Override19 public int hashCode() {20 return Objects.hash(code, price);21 }22}

Comprobar

La idea

Las cubetas se llenan

Cuando hay muchos pares, las cubetas se alargan y las búsquedas se vuelven lentas. Por eso un HashMap crece:

• Al principio hay 16 cubetas.
• Cuando hay más pares que el 75 % del número de cubetas, crea el doble de cubetas y reparte de nuevo todas las claves. El número de cubeta depende del número de cubetas, así que cada clave se calcula otra vez.
• Por eso, en promedio, put y get son rápidos, pero de vez en cuando un put tarda más.

También hay una trampa. Una clave no debe cambiar mientras está en un diccionario o en un conjunto:

Seat seat = new Seat(5, 12);
Set<Seat> sold = new HashSet<>();
sold.add(seat);

seat.number = 13;
System.out.println(sold.contains(seat));
System.out.println(sold.contains(new Seat(5, 12)));
System.out.println(sold.size());

Salida

false
false
1

El asiento se guardó en la cubeta de 5/12. Después su número pasó a ser 13, y el código hash cambió. contains(seat) busca en la cubeta de 5/13 y no lo encuentra. contains(new Seat(5, 12)) busca en la cubeta correcta, pero el objeto que está ahí ya no es igual a 5/12. El elemento está en el conjunto (el tamaño es 1), pero no se puede encontrar. Por eso conviene que los campos de una clave sean final.

Más precisamente, para curiosos

• Ese 75 % se llama factor de carga, y puedes fijarlo en el constructor: new HashMap<>(64, 0.75f). Si sabes cuántas claves habrá, da el número inicial de cubetas, y el diccionario no tendrá que crecer por el camino.
• Desde Java 8, una cubeta con más de 8 pares (TREEIFY_THRESHOLD) pasa de lista a árbol balanceado, si hay por lo menos 64 cubetas. Si al repartir de nuevo quedan 6 pares o menos en esa cubeta (UNTREEIFY_THRESHOLD), el árbol vuelve a ser una lista. Así, con muchas colisiones, una búsqueda en una cubeta con n pares hace unas log n comparaciones en lugar de n.

Ejercicio

Tus propios códigos hash

Resuelve las tareas en tu editor.

1. Un código hash para una persona. Una clase Person con nombre, apellido y edad. Sobrescribe equals y hashCode. Para hashCode, usa la receta: empieza en 17, y para cada campo, result = 31 * result + el hash del campo. Para un campo int, el hash es el propio número. Crea dos veces a Iván Pérez con 30 años y una vez con 31. Imprime los códigos hash y cuántas personas distintas quedan en un HashSet.

Salida

420260857
420260857
420260858
Personas distintas: 2

2. El robot del almacén. El robot empieza en la celda (0, 0) y hace los movimientos NNEESWWN: N es arriba (y + 1), S es abajo, E es a la derecha (x + 1), W es a la izquierda (W de west, oeste en inglés). ¿Cuántas celdas distintas visitó, contando la inicial? Guárdalas en un HashSet<Point>. Con esta clase el programa dice 9, pero debería decir 7. Corrígelo:

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Salida

Movimientos: 8
Celdas distintas: 7

3. El hash de un archivo. Un método hashFileContent(String filePath) lee el archivo y devuelve el código hash de su contenido como texto hexadecimal: Integer.toHexString(content.hashCode()). Escribe tres informes: a.txt y b.txt con «Informe de octubre: 1250 €», y c.txt con «Informe de octubre: 1260 €». Compara sus hashes. Hashes distintos significan que los archivos son distintos con seguridad. Hashes iguales significan «casi seguro que son iguales»: con un int es posible una colisión, así que para una comprobación de verdad se usa SHA-256.

Salida

a.txt: dfba5017
b.txt: dfba5017
c.txt: dfc86798
a y b: iguales
a y c: distintos

Más tareas

• Tu propia tabla hash. Una continuación de la tabla de usuarios de la lección anterior, esta vez sin HashMap. Crea un array de 8 cubetas, cada una un ArrayList de pares de nombre de usuario y correo. La función hash es la suma de los códigos de los caracteres del nombre. Escribe add, get y un método que imprima cuántos pares hay en cada cubeta.
• Un ID a partir de un correo. generateUserId(String email) devuelve "U" + Integer.toHexString(email.toLowerCase().hashCode()). ¿El ID es el mismo para Ivan@Example.com y ivan@example.com? ¿Pueden dos correos distintos recibir el mismo ID? ¿Cómo lo averiguarías?
• Contar colisiones. Calcula la cubeta de las claves user1 … user1000 con 16, 64 y 1024 cubetas, y cuenta cuántas claves caen en una cubeta que ya tiene una clave.
• La caja de zapatos. Una clase Box con ancho, alto y profundidad. Dos cajas son la misma si sus medidas son iguales, en el mismo orden. Escribe equals y hashCode con Objects.hash, y comprueba las cajas 30×20×10 y 10×20×30 en un HashSet.

Test

Ponte a prueba

1. ¿Qué hace un HashMap con el código hash de una clave?

Lo compara con todos los demás códigos hashCalcula a partir de él el número de la cubeta donde buscarLo guarda en lugar de la clave

2. Dos claves distintas tienen el mismo código hash. ¿Qué pasa?

La segunda borra la primeraHashMap lanza una excepciónLas dos quedan en una misma cubeta, y equals las distingue

3. a.equals(b) es true. ¿Qué debe cumplirse con sus códigos hash?

Tienen que ser distintosa.hashCode() == b.hashCode(), siempreNada

4. Usas tu propia clase Seat como clave sin sobrescribir equals y hashCode. ¿Qué devuelve get(new Seat(5, 12))?

null: el objeto nuevo es otro objeto, y el equals y el hashCode de Object no miran los camposLanza una excepciónEl valor guardado con put(new Seat(5, 12), …)

5. ¿Qué campo es seguro incluir en el hashCode de una clave?

Un número aleatorio elegido en el constructorUn campo que cambia mientras el objeto está en un HashSetUn campo que no cambia (final) y que equals también compara

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Archivos · Listas · Pila, cola y lista enlazada · HashMap y HashSet
• Continúa en: record, switch y patrones · Tabla hash · Contraseñas · Dependencias: el código ajeno que ejecuta el tuyo
• Ejercicios sobre el tema: Colecciones