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 GetHashCode(); Dictionary 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
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }
}

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "María";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Iván";
Console.WriteLine(bookings.Count);

Salida

False
1
2

María compró el asiento 5/12, pero ContainsKey con el mismo asiento dice False. 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 Dictionary 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 GetHashCode(). Todo objeto lo tiene, porque está en object.

Console.WriteLine("María".GetHashCode() == "María".GetHashCode());
Console.WriteLine("María".GetHashCode() == "Mario".GetHashCode());
Console.WriteLine("María".GetHashCode() == "maría".GetHashCode());
Console.WriteLine(1004.GetHashCode());

Salida

True
False
False
1004

• Dentro de una misma ejecución, el mismo texto da el mismo número.
• Un cambio pequeño da otro número: "María", "Mario" y "maría" son tres códigos hash distintos.
• El código hash de un int es el propio número.
• Un código hash se calcula rápido, sin importar cuántas claves haya en el diccionario.

Aquí no se imprime a propósito el número de un texto. .NET calcula el código hash de un string de forma distinta en cada ejecución del programa, así que te saldría otro. Las comparaciones salen igual siempre.

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

Más precisamente, para curiosos

• ¿Por qué cambia el código hash de un texto? Si se conociera de antemano, alguien podría enviar a un servidor miles de claves con el mismo código hash y volver lento el diccionario. Por eso .NET elige un punto de partida aleatorio para el cálculo en cada ejecución. El código hash de un texto no se guarda en un archivo ni en una base de datos, ni se envía a otro programa: allí es distinto.

• 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. GetHashCode() sirve para búsquedas rápidas y no da esa protección.

Míralo

Las cubetas

Por dentro, un Dictionary 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. El código hash de un texto cambia en cada ejecución, así que aquí las claves son números de pedido: para ellos, el código hash es el propio número:

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> cubeta " + index);
}

Paso a paso, en palabras

1. Cuatro claves (números de pedido) y ocho cubetas vacías, numeradas del 0 al 7.
2. 1007.GetHashCode() es el propio número, 1007. El resto de dividir entre 8 es 7: esa es la cubeta.
3. 2043 da la cubeta 3.
4. 3010 da la cubeta 2.
5. 4051 también cae en la cubeta 3: una colisión. Las dos claves están en una misma cubeta: 4051 cuelga detrás de 2043 como una cadena.
6. Se busca 4051: el mismo número, la misma cubeta 3. Equals con 2043: no. Con 4051: sí.

• Escribir bookings[clave] = … calcula la cubeta y guarda ahí el par. Buscar (ContainsKey, TryGetValue, [clave]) calcula la misma cubeta y busca solo en ella. Por eso es rápido incluso con un millón de claves.
• % en C#, igual que en Java, puede dar un número negativo: -7 % 8 es -7. Por eso se escribe (hash % buckets + buckets) % buckets: así el resto nunca es negativo. Un código hash puede ser negativo, pero un número de cubeta no.
• 2043 y 4051 cayeron en la cubeta 3. Esto se llama colisión. De eso trata la siguiente tarjeta.

Más precisamente, para curiosos

• El Dictionary real convierte el código hash en un número sin signo (uint), que nunca es negativo, y toma el resto de dividirlo entre el número de cubetas. Ese número es primo (3, 7, 17, 37…), así que allí los números son otros, pero el principio es el mismo.

Console.WriteLine(-7 % 8 + " " + (-7 % 8 + 8) % 8);

Salida

-7 1

Pruébalo

¿Qué cubeta?

El código hash de un int 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 };
foreach (int id in orderIds)
{
    Console.WriteLine(id + " -> cubeta " + id.GetHashCode() % 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: GetHashCode encuentra la cubeta, Equals encuentra la clave

Claves distintas pueden tener el mismo código hash. El código hash de un long es el «o» exclusivo (XOR) de su mitad superior y su mitad inferior, de 32 bits cada una. En -1 todos los bits son 1, las dos mitades se anulan, y queda 0, igual que para el propio 0:

Console.WriteLine(0L.GetHashCode() + " " + (-1L).GetHashCode());

Dictionary<long, string> codes = new Dictionary<long, string>();
codes[0L] = "cero";
codes[-1L] = "menos uno";
Console.WriteLine(codes[0L] + " " + codes[-1L]);

Salida

0 0
cero menos uno

Las dos claves están en una misma cubeta, pero el diccionario no las confunde. La cubeta guarda una cadena de pares. Una búsqueda la recorre y compara con Equals hasta encontrar la clave.

Así que los dos pasos funcionan así:

1. GetHashCode() 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 compara referencias, y GetHashCode 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 GetHashCode 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
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }

    public override int GetHashCode()
    {
        return 31 * Row + Number;
    }
}

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

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "María";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Iván";
Console.WriteLine(bookings.Count);

Salida

True
1
1

Las reglas que espera C#:

• Si a.Equals(b), entonces a.GetHashCode() == b.GetHashCode(). Siempre.
• Si los códigos hash son iguales, los objetos pueden ser distintos. Eso es una colisión.
• Si sobrescribes Equals, sobrescribe también GetHashCode, con las mismas propiedades.

Si sobrescribes solo Equals, el compilador te advierte, pero el programa compila:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }
}

Advertencia

warning CS0659: 'Seat' overrides Object.Equals(object o) but does not override Object.GetHashCode()

Con este Seat, el primer programa vuelve a imprimir False, 1 y 2: el asiento se vende dos veces. La advertencia no detiene al compilador, así que léela.

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 HashCode.Combine. Calcula un código hash a partir de los valores que le das:

public override int GetHashCode()
{
    return HashCode.Combine(Row, Number);
}

• El número de HashCode.Combine también cambia en cada ejecución, como el código hash de un texto. Para el diccionario eso no importa: dentro de una misma ejecución, asientos iguales tienen códigos hash iguales.
• Equals recibe un object, así que primero comprueba si el otro es siquiera un Seat. other is not Seat s es la comprobación de tipo del módulo «Herencia y polimorfismo»: si el otro es un Seat, s es ese objeto, ya del tipo Seat. Por eso new Seat(5, 12).Equals("5/12") es False.
• En C#, una clase que va a ser clave suele tener también IEquatable<Seat>: un método Equals(Seat other), sin conversión desde object. Dictionary y HashSet lo llaman cuando existe, y Equals(object) solo lo llama a él. Aquí las propiedades son de solo lectura. Verás por qué en la tarjeta «Las cubetas se llenan»:

class Seat : IEquatable<Seat>
{
    public int Row { get; }
    public int Number { get; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public bool Equals(Seat other)
    {
        return other is not null && Row == other.Row && Number == other.Number;
    }

    public override bool Equals(object other)
    {
        return Equals(other as Seat);
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Row, Number);
    }
}

• En el módulo «C# moderno» verás record. Con una línea, record Seat(int Row, int Number);, Equals y GetHashCode a partir de las propiedades quedan listos, y el primer programa imprime True, 1 y 1.

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:

HashSet<Product> catalog = new HashSet<Product>();
catalog.Add(new Product("A-100", 25.0));
// El precio bajó, pero es el mismo producto.
Console.WriteLine(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 Product2{3 public string Code { get; set; }4 public double Price { get; set; }56 public Product(string code, double price)7 {8 Code = code;9 Price = price;10 }1112 public override bool Equals(object other)13 {14 return other is Product p && Code == p.Code;15 }1617 public override int GetHashCode()18 {19 return HashCode.Combine(Code, Price);20 }21}

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 Dictionary crece:

• Al principio no hay cubetas. La primera vez que agregas algo, crea 3.
• Cuando los lugares se llenan, crea por lo menos el doble de cubetas (otra vez un número primo) 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. Aquí se ve cuándo crece:

Dictionary<string, int> prices = new Dictionary<string, int>();
int capacity = prices.EnsureCapacity(0);
for (int i = 1; i <= 20; i++)
{
    prices["producto " + i] = i;
    if (prices.EnsureCapacity(0) != capacity)
    {
        capacity = prices.EnsureCapacity(0);
        Console.WriteLine("Crece en el par " + i + ": " + capacity + " lugares");
    }
}

Salida

Crece en el par 1: 3 lugares
Crece en el par 4: 7 lugares
Crece en el par 8: 17 lugares
Crece en el par 18: 37 lugares

• EnsureCapacity(0) devuelve cuántos lugares tiene el diccionario, sin cambiar nada. Aquí sirve solo para ver cuándo cambia la tabla. En un Dictionary hay tantos lugares como cubetas.
• Por eso, en promedio, agregar y buscar son rápidos, pero de vez en cuando agregar algo 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);
HashSet<Seat> sold = new HashSet<Seat>();
sold.Add(seat);

seat.Number = 13;
Console.WriteLine(sold.Contains(seat));
Console.WriteLine(sold.Contains(new Seat(5, 12)));
Console.WriteLine(sold.Count);

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 las propiedades de una clave sean de solo lectura: public int Number { get; }.

Más precisamente, para curiosos

• Puedes fijar cuántos lugares hay al principio en el constructor: new Dictionary<string, int>(64). El diccionario toma un número primo que no sea menor (aquí 71), y con 64 claves no tiene que crecer por el camino. Cuándo crece (cuando se llenan los lugares) no se puede fijar.
• En .NET una cubeta siempre es una cadena: no hay árbol como en Java. Contra muchas colisiones provocadas a propósito con texto, lo que lo protege es que el código hash de un texto es distinto en cada ejecución.

Dictionary<string, int> prices = new Dictionary<string, int>(64);
Console.WriteLine(prices.EnsureCapacity(0));
for (int i = 1; i <= 64; i++)
{
    prices["producto " + i] = i;
}
Console.WriteLine(prices.EnsureCapacity(0));

Salida

71
71

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 GetHashCode. Para GetHashCode, 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 si los códigos hash de los dos primeros son iguales, si los códigos hash del primero y el tercero son iguales, y cuántas personas distintas quedan en un HashSet. No imprimas los códigos hash en sí: con texto cambian en cada ejecución.

Salida

True
False
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
{
    public int X { get; set; }
    public int Y { get; set; }

    public Point(int x, int y)
    {
        X = x;
        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 hash de su contenido como texto hexadecimal. GetHashCode() no sirve aquí: en la siguiente ejecución el mismo archivo tendría otro código hash. Usa SHA-256 de System.Security.Cryptography: Convert.ToHexStringLower(SHA256.HashData(Encoding.UTF8.GetBytes(content))) (Encoding está en System.Text). Un archivo se escribe con File.WriteAllText(path, text) y se lee con File.ReadAllText(path) (en System.IO). 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 archivos distintos, y hashes SHA-256 iguales significan, en la práctica, archivos iguales.

Salida

a.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
b.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
c.txt: 55326c55a315a74bbe791da3c40262c0e4186a48b0d4c098801c64390993b9b1
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 Dictionary. Crea un array de 8 cubetas, cada una una List 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" y los primeros 8 caracteres del SHA-256 del correo en minúsculas. ¿El ID es el mismo para Ivan@Example.com y ivan@example.com? ¿Por qué GetHashCode() no sirve aquí? ¿Pueden dos correos distintos recibir el mismo ID? ¿Cómo lo averiguarías?
• Contar colisiones. Calcula la cubeta de las claves user1 … user1000 con GetHashCode() para 16, 64 y 1024 cubetas, y cuenta cuántas claves caen en una cubeta que ya tiene una clave. Ejecuta el programa dos veces: el número cambia un poco, porque el código hash de un texto cambia.
• 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 GetHashCode con HashCode.Combine, y comprueba las cajas 30×20×10 y 10×20×30 en un HashSet.

Test

Ponte a prueba

1. ¿Qué hace un Dictionary 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 primeraEl Dictionary 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?

a.GetHashCode() == b.GetHashCode(), siempreNadaTienen que ser distintos

4. Usas tu propia clase Seat como clave sin sobrescribir Equals y GetHashCode. ¿Qué devuelve ContainsKey(new Seat(5, 12))?

False: el objeto nuevo es otro objeto, y el Equals y el GetHashCode de object no miran las propiedadesLanza KeyNotFoundExceptionTrue, si antes se guardó una clave new Seat(5, 12)

5. Sobrescribes Equals en Seat, pero no GetHashCode. ¿Qué pasa?

El programa no compilaEl Dictionary calcula el código hash a partir de Equals por su cuentaCompila con la advertencia CS0659, y el Dictionary sigue sin encontrar el asiento

6. ¿Qué propiedad es seguro incluir en el GetHashCode de una clave?

Una propiedad que no cambia (solo get) y que Equals también comparaUna propiedad que cambia mientras el objeto está en un HashSetUn número aleatorio elegido en el constructor

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: try, catch y finally · Listas · Pila, cola y lista enlazada · Dictionary 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