Un estudiante descubre por casualidad una nueva forma de almacenar datos

En otoño de 2021, el estudiante de la Universidad de Rutgers, Andrew Krapivin, se topó con un artículo científico titulado "Tiny Pointers" ("Punteros diminutos"), que cambiaría su vida. En aquel momento, el joven investigador apenas le prestó atención, pero dos años después, cuando decidió estudiarlo en detalle "simplemente por curiosidad", terminó revolucionando uno de los principios fundamentales de la informática.

Al analizar el artículo, Krapivin comenzó a pensar en cómo hacer los punteros aún más compactos para que ocuparan menos memoria. Estos elementos desempeñan un papel clave en el funcionamiento de las computadoras: actúan como señales de tráfico que dirigen el sistema hacia la ubicación de los datos almacenados. Cuanto menos espacio ocupe cada una de estas "señales", más eficientemente se usará la memoria.

Sin embargo, para crear punteros más compactos, era necesario reorganizar la propia información a la que apuntaban. El estudiante recurrió a las tablas hash, uno de los métodos fundamentales de almacenamiento de datos en los sistemas informáticos. Una tabla hash funciona como un índice inteligente: no solo almacena ciertos datos, sino que también permite encontrarlos, eliminarlos o añadir nuevos de forma casi instantánea.

Durante sus experimentos, Krapivin descubrió por accidente un nuevo tipo de tabla hash. Su singularidad radicaba en que encontraba los elementos necesarios mucho más rápido que las opciones existentes, reduciendo el número de pasos requeridos para la búsqueda.

Martin Farach-Colton, uno de los autores del artículo original sobre los "punteros diminutos" y exprofesor de Krapivin, recibió el hallazgo con escepticismo al principio. Las tablas hash han sido objeto de estudio desde principios de la década de 1950 y se consideran una de las estructuras más investigadas en la informática. La mejora propuesta parecía demasiado significativa para un campo tan bien explorado. Para verificar la idea del estudiante, Farach-Colton se dirigió a su colega William Kuszmaul, de la Universidad Carnegie Mellon.

La reacción de Kuszmaul sorprendió a todos: resultó que Krapivin no solo había mejorado una tabla hash, sino que también refutó un postulado científico en el que se había creído durante 40 años. En 1985, el renombrado informático Andrew Yao, futuro ganador del Premio Turing, propuso una hipótesis sobre la velocidad límite de las tablas hash de cierto tipo.

En su estudio, Yao afirmaba que el método más eficiente de búsqueda en una tabla hash era la exploración aleatoria de posiciones: el sistema verifica celdas en orden aleatorio hasta encontrar el elemento deseado o un espacio libre. Según su teoría, el tiempo de búsqueda aumentaba inevitablemente a medida que la tabla se llenaba. Si se expresa la ocupación de la tabla mediante un parámetro x (donde x=100 significa un 99% de llenado y x=1000 un 99,9%), entonces en el peor de los casos habría que revisar un número de celdas proporcional a x.

Sin embargo, al trabajar en la mejora de los "punteros diminutos", el estudiante desarrolló un método completamente nuevo de organización de datos. En lugar de una exploración aleatoria, su enfoque empleaba un algoritmo especial que determinaba las posiciones óptimas para colocar y buscar elementos. Así, incluso en los casos más complejos, con la tabla casi llena, el tiempo de búsqueda resultó ser proporcional a (log x)², lo que implica un crecimiento mucho más lento en comparación con la dependencia lineal del método de Yao.

Es decir, si la tabla estaba llena al 99,9% (x=1000), el método clásico requería en el peor de los casos revisar unas mil posiciones. En cambio, el nuevo algoritmo podía realizar la misma tarea con solo unas 100 operaciones. A medida que la ocupación de la tabla aumentaba, esta diferencia se volvía aún más significativa.

Pero la mayor sorpresa aún estaba por llegar. En el mismo estudio de 1985, Yao había analizado el tiempo medio de búsqueda en tablas hash que empleaban el llamado algoritmo "codicioso". Este enfoque coloca los nuevos elementos en la primera posición disponible, como si se estuviera llenando un auditorio desde la primera fila. Yao demostró que, en tales tablas, el tiempo medio de búsqueda no podía ser inferior a log x.

Los autores del nuevo trabajo decidieron comprobar si esta limitación se aplicaba también a las tablas hash con otros algoritmos de distribución de datos. Diseñaron una versión donde los elementos se organizaban según reglas más complejas y obtuvieron un resultado sorprendente: el tiempo medio de búsqueda resultó ser constante, sin depender en absoluto del grado de ocupación de la tabla.

"Este resultado fue una sorpresa incluso para nosotros", confesó Farach-Colton. "No podíamos imaginar que el tiempo de búsqueda pudiera permanecer constante sin importar la ocupación de la tabla". "Este descubrimiento podría habernos eludido durante otros cuarenta años", añadió Sepehr Assadi, de la Universidad de Waterloo. "Nos obliga a replantearnos por completo las capacidades de las tablas hash".

Si bien el descubrimiento aún no tiene aplicaciones prácticas inmediatas, su importancia para la informática es difícil de sobrestimar. "Comprender en profundidad las estructuras de datos fundamentales es crucial", destacó Alex Conway, de Cornell Tech. "Nunca podemos predecir cómo un hallazgo teórico se traducirá en resultados prácticos. Dado que las tablas hash están presentes en todo, desde motores de búsqueda hasta bases de datos, cualquier mejora en su eficiencia podría tener consecuencias de gran alcance".