Tabla hash

class Nodo:
    def __init__(self, clave, valor, siguiente):
        self.clave, self.valor, self.siguiente = clave, valor, siguiente


class Tabla:
    """Una tabla hash de texto a entero con encadenamiento: cada cubeta es una lista de nodos."""
    def __init__(self):
        self.cubetas = [None] * 7

    @staticmethod
    def hash(s):                                # como el de Java (el hash() de Python cambia en cada ejecución)
        h = 0
        for c in s:
            h = (31 * h + ord(c)) % 1_000_003
        return h

    def contar(self, clave):
        """Suma uno al valor de la clave (y la crea con 1 si no estaba)."""
        i = self.hash(clave) % len(self.cubetas)
        n = self.cubetas[i]
        while n is not None:
            if n.clave == clave:                # ya estaba
                n.valor += 1
                return
            n = n.siguiente
        self.cubetas[i] = Nodo(clave, 1, self.cubetas[i])   # nueva, al principio de su cubeta

    def mostrar(self):
        for i, n in enumerate(self.cubetas):
            partes = []
            while n is not None:
                partes.append(f"{n.clave}={n.valor}")
                n = n.siguiente
            print(f"cubeta {i}:" + "".join(" " + p for p in partes))


t = Tabla()
for p in "el gato y el perro y el raton".split():
    t.contar(p)
t.mostrar()

/** Una tabla hash de texto a número con encadenamiento: cada cubeta es una lista de nodos. */
class Tabla {
    cubetas = new Array(7).fill(null);

    static hash(s) {                                  // como String.hashCode de Java, sin desbordarse
        let h = 0;
        for (const c of s) h = (31 * h + c.charCodeAt(0)) % 1000003;
        return h;
    }

    /** Suma uno al valor de la clave (y la crea con 1 si no estaba). */
    contar(clave) {
        const i = Tabla.hash(clave) % this.cubetas.length;
        for (let n = this.cubetas[i]; n !== null; n = n.siguiente) {
            if (n.clave === clave) { n.valor++; return; }                        // ya estaba
        }
        this.cubetas[i] = { clave, valor: 1, siguiente: this.cubetas[i] };     // nueva, al principio de su cubeta
    }

    mostrar() {
        this.cubetas.forEach((primero, i) => {
            let linea = `cubeta ${i}:`;
            for (let n = primero; n !== null; n = n.siguiente) linea += ` ${n.clave}=${n.valor}`;
            console.log(linea);
        });
    }
}

const t = new Tabla();
for (const p of "el gato y el perro y el raton".split(" ")) t.contar(p);
t.mostrar();

using System;
using System.Text;

// Una tabla hash de string a int con encadenamiento: cada cubeta es una lista de nodos.
class Tabla {
    class Nodo {
        public readonly string Clave;
        public int Valor;
        public Nodo? Siguiente;
        public Nodo(string clave, int valor, Nodo? siguiente) { Clave = clave; Valor = valor; Siguiente = siguiente; }
    }

    private readonly Nodo?[] cubetas = new Nodo?[7];

    static int Hash(string s) {                       // como el de Java (GetHashCode cambia en cada ejecución)
        int h = 0;
        foreach (char c in s) h = (31 * h + c) % 1_000_003;
        return h;
    }

    // Suma uno al valor de la clave (y la crea con 1 si no estaba).
    public void Contar(string clave) {
        int i = Hash(clave) % cubetas.Length;
        for (var n = cubetas[i]; n != null; n = n.Siguiente) {
            if (n.Clave == clave) { n.Valor++; return; }                 // ya estaba
        }
        cubetas[i] = new Nodo(clave, 1, cubetas[i]);                     // nueva, al principio de su cubeta
    }

    public void Mostrar() {
        for (int i = 0; i < cubetas.Length; i++) {
            var sb = new StringBuilder(
quot;cubeta {i}:");
            for (var n = cubetas[i]; n != null; n = n.Siguiente) sb.Append(
quot; {n.Clave}={n.Valor}");
            Console.WriteLine(sb);
        }
    }
}

class Program {
    static void Main() {
        var t = new Tabla();
        foreach (var p in "el gato y el perro y el raton".Split(' ')) t.Contar(p);
        t.Mostrar();
    }
}

<?php
/** Una tabla hash de texto a entero con encadenamiento: cada cubeta es una lista de nodos. */
class Tabla {
    private array $cubetas;

    public function __construct() { $this->cubetas = array_fill(0, 7, null); }

    public static function hash(string $s): int {         // como String.hashCode de Java, sin desbordarse
        $h = 0;
        foreach (str_split($s) as $c) $h = (31 * $h + ord($c)) % 1000003;
        return $h;
    }

    /** Suma uno al valor de la clave (y la crea con 1 si no estaba). */
    public function contar(string $clave): void {
        $i = self::hash($clave) % count($this->cubetas);
        for ($n = $this->cubetas[$i]; $n !== null; $n = $n->siguiente) {
            if ($n->clave === $clave) { $n->valor++; return; }                     // ya estaba
        }
        $this->cubetas[$i] = (object) ["clave" => $clave, "valor" => 1, "siguiente" => $this->cubetas[$i]];   // nueva, al principio
    }

    public function mostrar(): void {
        foreach ($this->cubetas as $i => $n) {
            $linea = "cubeta $i:";
            for (; $n !== null; $n = $n->siguiente) $linea .= " {$n->clave}={$n->valor}";
            echo $linea, "\n";
        }
    }
}

$t = new Tabla();
foreach (explode(" ", "el gato y el perro y el raton") as $p) $t->contar($p);
$t->mostrar();

# En Python, __eq__ y __hash__ van de la mano: dos objetos iguales deben dar el mismo hash.
from dataclasses import dataclass


@dataclass(frozen=True)          # frozen: inmutable, y ya trae __eq__ y __hash__ con sus campos
class Punto:
    x: int
    y: int


class Alumno:
    def __init__(self, dni, nombre):
        self.dni, self.nombre = dni, nombre

    def __eq__(self, otro):
        return isinstance(otro, Alumno) and self.dni == otro.dni

    def __hash__(self):
        return hash(self.dni)    # los mismos campos que __eq__

// En JavaScript, Map y Set comparan los objetos por referencia: dos objetos con los mismos datos
// son claves distintas. Para usar «el mismo punto» como clave hay que construir una clave primitiva.
const visitados = new Set();
const clave = (p) => `${p.x},${p.y}`;      // dos puntos iguales dan el mismo texto

visitados.add(clave({ x: 1, y: 2 }));
visitados.has(clave({ x: 1, y: 2 }));      // true (con los objetos directamente sería false)

// En C#, Equals y GetHashCode van de la mano: dos objetos iguales deben dar el mismo hash.
record Punto(int X, int Y);                // un record ya trae Equals y GetHashCode con sus campos

class Alumno {
    private readonly string dni;
    public string Nombre { get; set; }

    public Alumno(string dni, string nombre) { this.dni = dni; Nombre = nombre; }

    public override bool Equals(object? o) => o is Alumno a && dni == a.dni;

    public override int GetHashCode() => dni.GetHashCode();   // los mismos campos que Equals
}

// En PHP, las claves de un array solo pueden ser enteros o textos: para usar un objeto como
// clave se construye un texto que lo identifique (o se usa SplObjectStorage, por identidad).
final class Punto {
    public function __construct(public readonly int $x, public readonly int $y) { }

    public function clave(): string { return "{$this->x},{$this->y}"; }   // dos puntos iguales, la misma clave
}

$visitados = [];
$visitados[(new Punto(1, 2))->clave()] = true;
isset($visitados[(new Punto(1, 2))->clave()]);   // true