Un joven informático y dos colegas demuestran que las búsquedas dentro de estructuras de datos llamadas tablas hash pueden ser mucho más rápidas de lo que hasta ahora se consideraba posible.
© Nash Weerasekera for Quanta MagazineLos « punteros diminutos », que muestran el camino hacia un dato almacenado, inspiraron la creación de un nuevo tipo de tabla hash más rápida.
En algún momento del otoño de 2021, Andrew Krapivin, estudiante de la Universidad de Rutgers, encontró un artículo que cambiaría su vida. En ese momento, Krapivin no le dio mucha importancia. Pero dos años más tarde, cuando por fin dedicó tiempo a leer el artículo («por diversión», según sus propias palabras), sus esfuerzos le llevaron a replantearse una herramienta muy utilizada en informática.
El título del artículo, «Tiny Pointers» (punteros diminutos), se refería a entidades en forma de flecha que pueden dirigirnos a una pieza de información, o elemento, en la memoria de un ordenador. A Krapivin pronto se le ocurrió una posible forma de miniaturizar aún más los punteros para que consumieran menos memoria. Sin embargo, para lograrlo, necesitaba una forma mejor de organizar los datos a los que apuntarían los punteros.
Recurrió a un método habitual de almacenamiento de datos conocido como tabla hash. Pero mientras jugueteaba, Krapivin se dio cuenta de que había inventado un nuevo tipo de tabla hash que funcionaba más rápido de lo esperado -tardando menos tiempo y dando menos pasos para encontrar elementos específicos.
Martín Farach-Colton, coautor del artículo «Tiny Pointers» y antiguo profesor de Krapivin en Rutgers, se mostró inicialmente escéptico ante el nuevo diseño de Krapivin. Las tablas hash se encuentran entre las estructuras de datos más estudiadas de toda la informática; el avance sonaba demasiado bueno para ser cierto. Pero para estar seguro, pidió a un colaborador habitual (y coautor de «Tiny Pointers»), William Kuszmaul, de la Universidad Carnegie Mellon, que comprobara el invento de su alumno. Kuszmaul tuvo una reacción diferente. «No sólo has inventado una tabla hash genial», recuerda que le dijo a Krapivin. «En realidad has echado por tierra una conjetura de hace 40 años».
Juntos, Krapivin (ahora estudiante de posgrado en la Universidad de Cambridge), Farach-Colton (ahora en la Universidad de Nueva York) y Kuszmaul demostraron en un artículo publicado en enero de 2025 que esta nueva tabla hash puede encontrar elementos más rápido de lo que se consideraba posible. Al hacerlo, habían refutado una conjetura considerada cierta durante mucho tiempo.
«Es un artículo importante», afirma Alex Conway, del Cornell Tech de Nueva York. «Las tablas hash son una de las estructuras de datos más antiguas que existen. Y siguen siendo una de las formas más eficientes de almacenar datos». Sin embargo, aún quedan preguntas abiertas sobre su funcionamiento, dijo. «Este artículo responde a un par de ellas de forma sorprendente».
Las tablas hash se han hecho omnipresentes en informática, en parte por su sencillez y facilidad de uso. Están diseñadas para permitir a los usuarios hacer exactamente tres cosas: «consultar» (buscar) un elemento, borrar un elemento o insertar uno en un hueco vacío. Las primeras tablas hash se remontan a principios de los años 50, y los informáticos las han estudiado y utilizado desde entonces. Entre otras cosas, los investigadores querían averiguar los límites de velocidad de algunas de estas operaciones. ¿Cuán rápida podía ser, por ejemplo, una nueva búsqueda o inserción?
La respuesta suele depender del tiempo que se tarda en encontrar un lugar vacío en una tabla hash. Esto, a su vez, suele depender de lo llena que esté la tabla hash. El grado de llenado puede describirse en términos de porcentaje global (esta tabla está llena al 50%, aquella al 90%), pero los investigadores suelen trabajar con tablas mucho más llenas. En su lugar, pueden utilizar un número entero, denotado por x, para especificar lo cerca que está la tabla hash del 100% de llenado. Si x es 100, la tabla está llena al 99%. Si x es 1.000, la tabla está llena al 99,9%. Esta medida de llenado ofrece una forma práctica de evaluar el tiempo que se tarda en realizar acciones como consultas o inserciones.
Los investigadores saben desde hace tiempo que, para determinadas tablas hash comunes, el tiempo esperado necesario para realizar la peor inserción posible -colocar un elemento en, digamos, el último lugar libre que queda- es proporcional a x. «Si tu tabla hash está llena al 99%», dijo Kuszmaul, «tiene sentido que tengas que mirar en unas 100 posiciones diferentes para encontrar un lugar libre».
En un artículo de 1985, el informático Andrew Yao, que acabaría ganando el premio A.M. Turing, afirmaba que entre las tablas hash con un conjunto específico de propiedades, la mejor forma de encontrar un elemento individual o un lugar vacío es simplemente recorrer los lugares potenciales al azar, un enfoque conocido como sondeo uniforme. También afirmó que, en el peor de los casos, es decir, cuando se busca el último punto vacío, nunca se puede obtener un resultado mejor que x. Durante 40 años, la mayoría de los informáticos asumieron que la conjetura de Yao era cierta.
© Phillip Ammon for Quanta MagazineAndrew Krapivin en el King's College Bridge de la Universidad de Cambridge. Su nueva tabla hash puede encontrar y almacenar datos más rápido de lo que los investigadores jamás creyeron posible.
«Este resultado es magnífico porque aborda y resuelve un problema tan clásico», afirma Guy Blelloch, de Carnegie Mellon.
«No sólo han refutado [la conjetura de Yao], sino que han encontrado la mejor respuesta posible a su pregunta», afirma Sepehr Assadi, de la Universidad de Waterloo. «Podríamos haber pasado otros 40 años antes de conocer la respuesta correcta».
Además de refutar la conjetura de Yao, el nuevo artículo también contiene lo que muchos consideran un resultado aún más sorprendente. Se refiere a una situación relacionada, aunque ligeramente distinta: En 1985, Yao analizó no sólo los tiempos de consulta en el peor de los casos, sino también el tiempo medio de todas las consultas posibles. Demostró que las tablas hash con determinadas propiedades -incluidas las denominadas «codiciosas», lo que significa que los nuevos elementos deben colocarse en el primer lugar disponible- nunca podrían lograr un tiempo medio mejor que log x.
Farach-Colton, Krapivin y Kuszmaul querían comprobar si ese mismo límite se aplicaba también a las tablas hash no codiciosas. Demostraron que no era así proporcionando un contraejemplo, una tabla hash sin vicios con un tiempo medio de consulta mucho, mucho mejor que log x. De hecho, no depende de x en absoluto. «Obtienes un número», dijo Farach-Colton, "algo que es simplemente una constante y no depende de lo llena que esté la tabla hash". El hecho de que se pueda conseguir un tiempo medio de consulta constante, independientemente de la capacidad de la tabla hash, fue totalmente inesperado, incluso para los propios autores.
Puede que los resultados del equipo no conduzcan a ninguna aplicación inmediata, pero eso no es lo único que importa, dijo Conway. «Es importante comprender mejor este tipo de estructuras de datos. No sabes cuándo un resultado como éste desbloqueará algo que te permita hacerlo mejor en la práctica.»
Steve Nadis
Steve Nadis es colaborador de la revista Quanta. Vive en Cambridge, Massachusetts. Sus artículos han aparecido en numerosas revistas, entre ellas Discover y Astronomy. Es coautor, más recientemente, de The Gravity of Math [La gravedad de las matemáticas] (Basic Books, 2024).
Comentarios del Lector
a nuestro Boletín