El descubrimiento que puede acelerar todo Internet

Descubrimiento informático. Andrew Krapivin, un joven matemático estadounidense, ha refutado una teoría que se consideraba inquebrantable durante 40 años. Revolucionó la idea de las capacidades del uso de las Tablas de Hash en las búsquedas de Internet acelerando las búsquedas aleatorias mediante un método asequible.

Andrew-Krapivin.webp

Andrew Krapivin el joven que revolucionó Internet

En reciente informe de Meduza, el periodista científico, Ilya Kabanov, explica cómo se estructuran las tablas hash, por qué es importante el éxito de Krapivin y si afectará la eficiencia del trabajo con datos en el futuro.

Descubrimiento: aceleración de búsqueda por tabla Hash

Una tabla hash es una estructura de información diseñada para gestionar y almacenar datos de manera que permita acceder a ellos y modificarlos con alta eficiencia. Funciona almacenando elementos asociados a pares clave-valor, facilitando operaciones como agregar, eliminar o buscar valores mediante su clave correspondiente.

El mecanismo central de estas tablas son las funciones hash, algoritmos que transforman claves en índices numéricos. Estos índices indican la posición exacta de los datos dentro de un arreglo, evitando la necesidad de recorrer toda la estructura para localizar un elemento. Por ejemplo, imagine una biblioteca donde cada libro tiene un código único (clave) asignado a un estante específico. En lugar de revisar cada libro, el usuario consulta un sistema de catalogación (función hash) que indica la ubicación precisa (índice) del libro deseado.

Las funciones hash buscan distribuir los datos de forma equilibrada en la tabla para reducir colisiones, es decir, situaciones donde múltiples elementos comparten la misma posición. Aun así, las colisiones pueden ocurrir, por lo que las tablas suelen incluir métodos de resolución, como listas enlazadas en celdas conflictivas. Esta eficiencia las hace esenciales en aplicaciones digitales, como bases de datos o servicios web, donde los usuarios exigen respuestas rápidas sin esperas prolongadas.

Tabla Hush.png

Tabla Hash

No obstante, el rendimiento de una tabla hash depende de su factor de carga (proporción entre elementos almacenados y capacidad total). Si la tabla se satura, aumentan las colisiones y el tiempo de búsqueda, lo que puede requerir ajustar su tamaño o rediseñar la función hash para mantener la eficacia. Por esto, su implementación óptima requiere equilibrar espacio en memoria y velocidad de operaciones.

Internet: las tablas Hash habían alcanzado su límite, pero...

En las tablas hash de direccionamiento abierto, uno de los dos tipos más comunes de tablas hash (el otro está basado en listas), los datos se almacenan directamente en una matriz de celdas. Cada celda puede estar vacía o contener una clave específica. Cuando es necesario insertar una nueva clave, se utiliza una secuencia de funciones hash para determinar las posibles posiciones en la matriz donde colocarla.

La tarea es encontrar una celda vacía utilizando funciones hash. La cantidad de pasos necesarios para realizar esto se denomina complejidad de búsqueda. De hecho, es esto lo que determina el rendimiento de las operaciones con tablas hash.

El objetivo de los desarrolladores es reducir la complejidad de la búsqueda, especialmente en condiciones en que la tabla está casi completamente llena . En términos sencillos, definiríamos la ocupación como un porcentaje: digamos que una mesa está ocupada en un 50% o en un 80%. A su vez, los investigadores utilizan el valor x para mostrar qué tan cerca está la tabla de llenarse al 100%. Si x es 100, entonces la tabla está llena al 99%, y si x es 1000, entonces está llena al 99,9%.

Investigación antecedente

En 1985, Andrew Yao, premio Turing, estableció que en tablas hash con direccionamiento abierto, la búsqueda óptima de elementos o celdas vacías requería probar ubicaciones al azar ("hashing universal"). Además, demostró que en el peor caso —como buscar la última celda libre en una tabla 99% llena— el tiempo necesario sería proporcional a revisar unas 100 posiciones. Esta teoría se consideró válida durante cuatro décadas.

Sin embargo, en enero de 2025, Andrew Krapivin, un estudiante de posgrado de la Universidad de Cambridge, y sus colegas refutaron la hipótesis de Yao, demostrando que las tablas hash podían optimizarse más allá de lo previsto. Este hallazgo sorprendió a la comunidad científica, que no había anticipado tales mejoras en la eficiencia de estas estructuras.

El descubrimiento de Krapivin

A finales de 2021, Andrew Krapivin, entonces estudiante de la Universidad de Rutgers, descubrió un artículo sobre cómo reducir el tamaño de los punteros en memoria. Al retomar años después esa idea, entendió que podía optimizarlos aún más si mejoraba la organización de los datos asociados. Esto lo llevó a explorar tablas hash, donde accidentalmente desarrolló un nuevo tipo de estructura, más rápida y eficiente, que permitía localizar elementos con menos tiempo y recursos.

Al compartir su hallazgo con su profesor, Martin Farah-Colton (coautor del artículo original sobre punteros), este mostró escepticismo inicial, dada la exhaustiva investigación previa en tablas hash. Sin embargo, al involucrar a William Kuzmal, de Carnegie Mellon, se confirmó que Krapivin no solo había creado una tabla innovadora, sino que había refutado la hipótesis de Yao (vigente durante 40 años) sobre la necesidad de búsqueda aleatoria en tablas casi llenas. Curiosamente, Krapivin desconocía el trabajo de Yao, lo que quizás le permitió romper paradigmas establecidos.

Junto a Farah-Colton y Kuzmal (ahora como estudiante de posgrado en Cambridge), publicaron un método que logra tiempo constante de búsqueda, independientemente del nivel de llenado de la tabla, superando incluso el "hashing universal". Aunque su impacto inmediato es limitado, el avance podría optimizar procesos en Internet e inspirar nuevas investigaciones. De hecho, tras su publicación, surgió otro estudio proponiendo estrategias de búsqueda dinámicas basadas en la ocupación de celdas, evidenciando su influencia en el campo.