Vía Meduza
Cada vez que abre la lista de contactos de su teléfono, busca un producto en una tienda en línea o revisa su correo electrónico, estructuras de datos especiales llamadas tablas hash lo ayudan a recuperar rápidamente la información que necesita. Es gracias a ellos que Internet moderno funciona básicamente como estamos acostumbrados. Pero se pensaba que el rendimiento de las tablas hash tenía un límite. Un descubrimiento casual de un joven estudiante de postgrado, Andrew Krapivin, revolucionó la idea de las capacidades de este instrumento. El periodista científico y autor del canal de Telegram Lifelong Flour, 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.
Primero , un poco más de detalle sobre qué son las tablas hash y por qué son necesarias
Una tabla hash es una estructura de datos, o una forma de organizar y almacenar información, que le ayuda a acceder y modificar datos de manera eficiente. Las tablas hash almacenan pares clave-valor y permiten realizar operaciones en ellos: agregar nuevos pares, eliminar los existentes y buscar un valor por clave.
Utilizan funciones hash: transformaciones que calculan un índice que apunta a la ubicación de los datos en una matriz. Cuando un usuario quiere buscar algo en una tabla hash, el sistema no recorre todo el conjunto de datos, sino que encuentra inmediatamente el valor deseado utilizando el índice calculado, acelerando significativamente la búsqueda.
Quizás el análogo más simple de una tabla hash en el mundo real es una biblioteca, donde cada libro se almacena en un lugar específico en un estante, designado por un número de identificación (clave). En lugar de buscar un libro en toda la colección de la biblioteca, el lector sólo necesita consultar el catálogo (función hash), que calcula la ubicación exacta (índice) del volumen deseado en el estante.
Una función hash distribuye los datos de manera uniforme en una tabla, minimizando la probabilidad de que muchos elementos terminen en la misma celda y creen colisiones. Gracias a esto, las tablas hash se han vuelto populares en los servicios de Internet modernos: los usuarios no quieren perder tiempo extra esperando mientras el sistema revisa los datos en la base de datos.
El problema es que la eficiencia de la tabla depende de su grado de plenitud: la relación entre el número de elementos almacenados y el tamaño de la matriz. A medida que la tabla se llena, aumenta el número de posibles colisiones y pueden ser necesarios más pasos para realizar la búsqueda.
¿Por qué se pensó que las tablas hash habían alcanzado su límite antes del descubrimiento de Krapivin?
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%.
En su artículo de 1985 , el científico informático Andrew Yao , que más tarde ganó el premio Turing , demostró que para las tablas hash con direccionamiento abierto, la mejor forma de encontrar un elemento o una celda vacía es probar aleatoriamente las posibles ubicaciones. Este enfoque se denomina «hashing universal». Yao también sugirió que en el peor de los casos, cuando es necesario encontrar la última celda libre, es imposible hacerlo sin gastar un tiempo proporcional a x . Si la tabla hash está llena en un 99%, probablemente tendrás que revisar alrededor de 100 posiciones diferentes para encontrar espacio libre.
Durante cuatro décadas, la mayoría de los investigadores creyeron que la hipótesis de Yao describía con precisión la realidad. Pero en enero de 2025, un joven estudiante de posgrado de la Universidad de Cambridge, Andrew Krapivin, junto con un par de colegas, demostró que el clásico estaba equivocado y la comunidad científica no se dio cuenta de que las tablas hash podrían hacerse aún más eficientes.
¿Qué exactamente pudo demostrar Krapivin y por qué el descubrimiento fue accidental?
A finales de 2021, el entonces estudiante de la Universidad de Rutgers, Andrew Krapivin (así se presenta el investigador en su reciente presentación ; en 2020, en una conversación con su abuelo que vivía en Ucrania, se hizo llamar Andrey) se topó accidentalmente con una publicación sobre la reducción del tamaño de los punteros en la memoria de la computadora. Unos años más tarde, volvió a este artículo, lo releyó y se dio cuenta de que era posible hacer que los punteros ocuparan incluso menos memoria. Sin embargo, para ello es necesario mejorar la organización de los datos a los que apuntarán los punteros.
Krapivin centró su atención en las tablas hash y, en el proceso de trabajar en ellas, inesperadamente creó un nuevo tipo de ellas, que resultó ser significativamente más rápido. Su tabla permitía encontrar los elementos en menos tiempo y con menos esfuerzo.
El estudiante se acercó a su profesor, Martin Farah-Colton, coautor del artículo sobre punteros. El profesor se mostró escéptico ante la idea: las tablas hash se han estudiado en gran detalle y parece que no se puede decir nada nuevo en este ámbito. Pero cuando Farah-Colton le pidió a su colega William Kuzmal, de la Universidad Carnegie Mellon, que comprobara el trabajo de Krapivin, se dio cuenta inmediatamente de que estaba hablando de un verdadero descubrimiento.
Kuzmal le dijo a Krapivin que no solo había creado una nueva tabla hash, sino que había refutado una hipótesis que había permanecido indiscutida durante 40 años. Lo más sorprendente es que Krapivin simplemente no conocía el trabajo de Yao; tal vez por eso no se dejó limitar por la sabiduría convencional.
Junto con Farah-Colton y Kuzmal, él (ahora estudiante de posgrado en Cambridge) preparó un artículo que describe un método que permite encontrar elementos más rápido que mediante una búsqueda aleatoria, incluso si la tabla está casi completamente llena. Su método no sólo hace que la búsqueda sea más rápida, sino que también permite buscar datos en tiempo constante, sin importar cuán llena esté la tabla.
Aunque es poco probable que el descubrimiento produzca cambios inmediatos, el método de Krapivin y sus colegas podría acelerar potencialmente muchos procesos en Internet. Como mínimo, inspirarán más investigaciones. Más precisamente, ya son inspiradores: poco después de la publicación de su artículo , apareció otro artículo que proponía un nuevo modelo para adaptar dinámicamente la estrategia de búsqueda dependiendo de qué celdas de la tabla ya estuvieran ocupadas.
