Visualizador de tabla hash

Hash tables employ deterministic mathematical algorithms to map arbitrary keys to finite index spaces, optimizing for O(1) temporal retrieval. Collisions, an inevitable consequence of the pigeonhole principle, necessitate strict resolution protocols. Chaining relies on linked list allocations, while linear and quadratic probing use mathematical step functions to navigate array indices. The load factor continuously dictates the statistical probability of these computationally expensive collisions.

Una tabla hash es simplemente un array acompañado de una regla — la función hash — que convierte cualquier clave en un número de casilla. En vez de recorrer cada entrada una por una, calculas dónde debe estar un elemento y vas directo allí; por eso las búsquedas siguen siendo rápidas incluso con millones de claves. El truco: la velocidad depende de repartir las claves de forma uniforme. Inserta unas cuantas aquí y observa qué rápido dos claves quieren la misma casilla.

Como una tabla hash degenera en una lenta búsqueda lineal cuando demasiadas claves caen en la misma casilla — justo el peor caso que puedes provocar arriba —, un atacante que conozca tu función hash puede fabricar miles de claves que colisionan a propósito. En 2011 este truco de 'hash-flooding' bloqueó servidores web en PHP, Java, Python y Ruby con una sola petición manipulada. La solución fueron funciones hash con semilla aleatoria como SipHash, hoy estándar en muchos lenguajes.