Hashing y tablas hash

📐 Fundamento

Una función hash es $h: K \to \mathbb{Z}$ — toma una clave de cualquier tipo y devuelve un entero.

Propiedades deseables:

1. Determinismo. Misma clave → mismo hash, siempre.
2. Rapidez. $O(1)$ o $O(L)$ para una clave de longitud $L$.
3. Distribución uniforme. Hashes parecen aleatorios — bajan colisiones.
4. Buen efecto avalancha. Cambio chico en la clave → cambio grande en el hash.

No es: un hash NO es único — dos claves pueden hashear al mismo número (colisión). Es matemáticamente inevitable cuando hay más claves posibles que números (siempre).

Hashes en Python:

hash("ana")          # algún entero
hash(42)             # 42 (Python hashea ints a sí mismos)
hash((1, 2, 3))      # tupla hashable
hash([1, 2, 3])      # TypeError — listas no son hashables

Python randomiza el hash de strings al iniciar el proceso (PYTHONHASHSEED). Eso evita que un atacante envíe claves diseñadas para colisionar (ataque de denegación de servicio).

Funciones hash simples

Modular para enteros:

def hash_int(x, tabla_size):
    return x % tabla_size

Funciona bien si tabla_size es primo (mejor distribución).

Polinomial para strings:

def hash_str(s, tabla_size):
    h = 0
    for c in s:
        h = (h * 31 + ord(c)) % tabla_size
    return h

El "31" es típico (es primo y tiene buenas propiedades de bits). Java usa 31 para String.hashCode(). Eso te da una idea de qué constantes funcionan bien.

📐 Fundamento

Idea: un array tabla de tamaño $m$. Para guardar (clave, valor):

1. Calculás pos = hash(clave) % m.
2. Guardás (clave, valor) en tabla[pos].

Para buscar clave: vas a tabla[hash(clave) % m]. Comparás la clave (¡puede haber colisión!).

class TablaHash:
    def __init__(self, m=8):
        self.m = m
        self.tabla = [None] * m
        self.n = 0

    def _hash(self, k):
        return hash(k) % self.m

    def put(self, k, v):
        i = self._hash(k)
        # Sin manejo de colisiones (ingenuo)
        self.tabla[i] = (k, v)
        self.n += 1

    def get(self, k):
        i = self._hash(k)
        entrada = self.tabla[i]
        if entrada is None or entrada[0] != k:
            return None
        return entrada[1]

Esto funciona... hasta la primera colisión. Si dos claves caen en la misma posición, la última pisa la primera. Necesitás resolver colisiones.

📐 Fundamento

Chaining (encadenamiento): cada celda de la tabla guarda una lista de pares (clave, valor) que cayeron ahí.

class TablaHashChaining:
    def __init__(self, m=8):
        self.m = m
        self.tabla = [[] for _ in range(m)]
        self.n = 0

    def put(self, k, v):
        i = hash(k) % self.m
        for j, (kk, _) in enumerate(self.tabla[i]):
            if kk == k:
                self.tabla[i][j] = (k, v)   # actualizar
                return
        self.tabla[i].append((k, v))
        self.n += 1

    def get(self, k):
        i = hash(k) % self.m
        for kk, v in self.tabla[i]:
            if kk == k: return v
        return None

    def remove(self, k):
        i = hash(k) % self.m
        for j, (kk, _) in enumerate(self.tabla[i]):
            if kk == k:
                self.tabla[i].pop(j)
                self.n -= 1
                return True
        return False

Análisis:

• En el caso ideal (distribución uniforme), cada chain tiene en promedio $n/m$ elementos.
• $n/m$ se llama factor de carga (load factor), $\alpha$.
• Operaciones: $O(1 + \alpha)$ promedio.
• Si $\alpha$ es chico (digamos < 1), promedio $O(1)$.
• Peor caso: todas las claves caen en la misma celda → $O(n)$.

Mantenimiento: cuando $\alpha$ supera un umbral (típicamente 0.75), rehash: crear una tabla más grande y migrar todo. Costo $O(n)$ pero amortizado $O(1)$ por operación.

📐 Fundamento

Open addressing (direccionamiento abierto): todos los pares viven directo en el array, sin listas. Si hay colisión, buscás la próxima celda libre.

Linear probing:

def put(self, k, v):
    i = hash(k) % self.m
    while self.tabla[i] is not None:
        if self.tabla[i][0] == k:
            self.tabla[i] = (k, v)   # actualizar
            return
        i = (i + 1) % self.m
    self.tabla[i] = (k, v)
    self.n += 1

Variantes:

• Linear: $h(k) + 1, h(k) + 2, \ldots$
• Quadratic: $h(k) + 1, h(k) + 4, h(k) + 9, \ldots$
• Double hashing: $h(k) + g(k), h(k) + 2 g(k), \ldots$

Pros: mejor uso de cache (todo está en un solo array, contiguo).

Cons: clustering — colisiones tienden a juntarse y degradar performance. Linear probing es el peor; quadratic y double hashing mitigan.

Eliminación es complicada. Si simplemente borrás una celda, podés "romper" la cadena de probing para otras claves. Solución: marcar como tombstone (lápida) en lugar de borrar.

Cuál usar. Las implementaciones reales:

• Java HashMap: chaining (con conversión a árbol Red-Black si una bucket pasa de 8 elementos).
• Python dict: open addressing con probing inteligente.
• C++ std::unordered_map: chaining.

Cada DBMS y lenguaje hace sus propias optimizaciones. La elección no es absoluta.

📐 Fundamento

Hash criptográfico (SHA-256, MD5, SHA-3) tiene requisitos extras:

1. Resistencia a preimagen. Dado $h(x)$, encontrar $x$ debe ser inviable.
2. Resistencia a segunda preimagen. Dado $x$, encontrar $y \neq x$ con $h(x) = h(y)$ debe ser inviable.
3. Resistencia a colisiones. Encontrar cualquier $x \neq y$ con $h(x) = h(y)$ debe ser inviable.

Eso los hace lentos (decenas de veces más que un hash de tabla) — porque la lentitud frustra ataques por fuerza bruta.

Distinción crucial:

Nunca uses MD5 ni SHA-1 para seguridad nueva. Están rotos (se han encontrado colisiones). Para passwords usá bcrypt, argon2, scrypt — están diseñados para ser lentos y resistentes a hardware específico.

import hashlib

# Para integridad / firma
h = hashlib.sha256(b"datos").hexdigest()
print(h)    # 64 caracteres hex

# Para passwords (bcrypt; pip install bcrypt)
import bcrypt
hashed = bcrypt.hashpw(b"contrasena", bcrypt.gensalt())
print(bcrypt.checkpw(b"contrasena", hashed))     # True

📐 Fundamento

Un filtro de Bloom es una estructura probabilística para test de pertenencia con memoria mínima y falsos positivos (pero nunca falsos negativos).

Cómo funciona: un array de bits de $m$ posiciones, $k$ funciones hash. Para insertar x, setear los bits en posiciones $h_1(x), h_2(x), \ldots, h_k(x)$. Para test, chequear que todos esos bits están en 1.

• Si alguno es 0: $x$ no está (seguro).
• Si todos son 1: $x$ probablemente está (chance de falso positivo).

Ventaja: memoria diminuta. Para 1 millón de elementos con 1% falsos positivos, ~1 MB. Una tabla hash igual ocuparía decenas de MB.

Aplicaciones:

• Detectar URLs visitadas (Chrome).
• Cache miss reducer (el bloom filter dice "no está en cache" sin tocar disco).
• Spell checkers ligeros.
• Bases de datos: descartar lecturas innecesarias.

(No los implementamos a fondo aquí; se ven en cursos de algoritmos avanzados.)