Hace unos 70 años, un ingeniero de IBM llamado Hans Peter Luhn cambió silenciosamente el rumbo de la informática. Luhn ya poseía varias patentes, incluida una para un dispositivo que podía medir el número de hilos de una tela y otra para una guía que determinaba qué bebidas mezcladas se podían preparar con los ingredientes de su cocina. Pero en un artículo interno de IBM de 1953, propuso una nueva técnica para almacenar y recuperar información que ahora está integrada en casi todos los sistemas computacionales: la tabla hash.

Las tablas hash son una clase importante de estructuras de datos. Ofrecen un método especialmente conveniente para acceder y alterar información en bases de datos masivas. Pero esta tecnología conlleva una compensación inevitable.

En un estudio clínico realizado en 1957 publicado en el Revista de investigación y desarrollo de IBM, W. Wesley Peterson identificó el principal desafío técnico que plantean las tablas hash: deben ser rápidas, es decir, que puedan recuperar rápidamente la información necesaria. Pero también deben ser compactos y utilizar la menor cantidad de memoria posible. Estos dos objetivos gemelos están fundamentalmente en desacuerdo. El acceso y la modificación de una base de datos se pueden realizar más rápidamente cuando la tabla hash tiene más memoria; y las operaciones se vuelven más lentas en tablas hash que utilizan menos espacio. Desde que Peterson planteó este desafío, los investigadores han intentado encontrar el mejor equilibrio entre tiempo y espacio.

Los informáticos han demostrado matemáticamente que han encontrado el equilibrio óptimo. La solución vino de un par de reciente papeles que se complementaban. "Estos artículos resuelven la pregunta abierta desde hace mucho tiempo sobre las mejores compensaciones posibles entre el espacio y el tiempo, arrojando resultados profundamente sorprendentes que espero que tengan un impacto significativo durante muchos años por venir", dijo Michael Mitzenmacher, un informático de la Universidad de Harvard que no participó en ninguno de los estudios.

"Definitivamente diría que es un gran problema", añadió Rasmus Pagh, informático de la Universidad de Copenhague. “Mucha gente ha trabajado en este problema, tratando de ver cuánto se puede exprimir el espacio y al mismo tiempo realizar operaciones eficientes en el tiempo. Éste es el que me hubiera encantado resolver”.

Hacer un hachís

Las tablas hash se encuentran entre las estructuras de datos más antiguas, simples, rápidas y utilizadas en la actualidad. Están diseñados para realizar tres operaciones básicas: inserciones, que agregan nuevos elementos a la base de datos; consultas, que acceden a un elemento o verifican si existe; y eliminaciones. Una tabla hash puede ser efímera (existir sólo mientras se ejecuta un programa en particular) o puede ser una parte permanente del sistema operativo de su computadora. Un navegador web como Chrome o Safari puede tener varias tablas hash integradas destinadas a realizar un seguimiento de diferentes tipos de datos.

Las entradas en una tabla hash se almacenan como pares, con el elemento (la información en sí) conectado a una clave que identifica la información. Introduzca una clave en el algoritmo de consulta de una tabla hash y le llevará directamente al elemento. Puede que esto no parezca tan extraordinario, pero para bases de datos enormes puede suponer un gran ahorro de tiempo.

Para tomar un ejemplo extremadamente simplificado, consideremos el Oxford English Dictionary, que tiene definiciones para más de 600,000 palabras. Si una edición digital se basa en una tabla hash, simplemente puede usar una palabra determinada como clave y proceder directamente a la definición. Sin una tabla hash, el diccionario probablemente dependería de un mecanismo de búsqueda mucho más lento, utilizando un proceso de eliminación para eventualmente converger en la definición solicitada. Y aunque una tabla hash puede encontrar cualquier palabra en un período de tiempo constante (normalmente una pequeña fracción de segundo), el tiempo de búsqueda para otros métodos puede aumentar a medida que aumenta el número de palabras en el diccionario. Una tabla hash también ofrece otra ventaja: puede mantener el diccionario dinámico, lo que facilita la inserción de nuevas palabras y la eliminación de las obsoletas.

Los investigadores han pasado décadas creando tablas hash que intentan maximizar la velocidad y minimizar la memoria. En el siglo XX, las soluciones tendían a ofrecer beneficios significativos en un solo aspecto, tiempo o espacio. Luego, en 20, los investigadores mostró que era teóricamente posible dar un gran salto de eficiencia tanto en el tiempo como en el espacio simultáneamente. Sin embargo, los investigadores tardarían otras dos décadas en encontrar el equilibrio ideal entre ambos.

La mezcla de datos

El primer gran paso hacia ese objetivo se produjo en 2022 a una importante conferencia de informática en Roma. Allí, un equipo propuso una tabla hash con nuevas características que podrían ofrecer la mejor combinación de eficiencia de tiempo y espacio jamás concebida. El primer autor del artículo (en orden alfabético) fue Michael Bender de la Universidad Stony Brook, por lo que comúnmente se lo conoce como Bender et al. tabla de picadillo. Si bien el equipo no intentó construir una tabla hash funcional, demostraron que, en principio, podría construirse con las características que describieron.

Para evaluar la tabla hash que idearon, el grupo produjo una curva de compensación: un gráfico que traza el tiempo por operación (inserción o eliminación) en un eje y el espacio ocupado por la memoria en el otro. Pero este gráfico define el espacio de una manera especial: debido a cómo están construidas, las tablas hash necesitan más memoria que la mínima necesaria para almacenar un conjunto determinado de elementos. Los científicos informáticos llaman a este espacio extra “bits desperdiciados”, aunque en realidad no están desperdiciados y, hasta cierto punto, son necesarios. El eje espacial de una curva de compensación mide el número de bits desperdiciados por clave.

Al analizar una curva de compensación, los investigadores pueden calcular el tiempo más rápido posible para una tabla hash que utiliza una cantidad determinada de espacio. También pueden invertir la pregunta para calcular el espacio más pequeño posible para un tiempo de operación determinado. Por lo general, un pequeño cambio en una variable conducirá a un pequeño cambio en la otra, dijo William Kuszmaul, científico informático teórico de Harvard y coautor del artículo de 2022. "Si duplicas el tiempo, quizás reduzcas a la mitad el número de bits desperdiciados por clave".

Pero ese no es el caso de la tabla hash que diseñaron. "Si aumentas el tiempo un poco, los bits desperdiciados por clave disminuyen exponencialmente", dijo Kuszmaul. La curva de compensación era tan pronunciada que literalmente estaba fuera de serie.

El equipo construyó su tabla hash en dos partes. Tenían una estructura de datos primaria, en la que los elementos se almacenan sin desperdiciar ningún bit, y una estructura de datos secundaria, que ayuda a una solicitud de consulta a encontrar el elemento que está buscando. Si bien el grupo no inventó la noción de una estructura de datos secundaria, sí hicieron un descubrimiento crucial que hizo posible su tabla hash hipereficiente: la eficiencia general de la memoria de la estructura depende de cómo la estructura primaria organiza sus elementos almacenados.

La idea básica es que cada artículo en la estructura primaria tiene ubicaciones de almacenamiento preferidas: una mejor ubicación, una segunda mejor, una tercera mejor, etc. Si un elemento está en su mejor lugar, se le asigna el número 1 y ese número se almacena en la estructura de datos secundaria. En respuesta a una consulta, la estructura secundaria proporciona solo el número 1, que detalla la ubicación exacta del elemento en la estructura primaria.

Si el artículo está en su mejor lugar número 100, la estructura de datos secundaria adjunta el número 100. Y debido a que el sistema usa binario, representa el número 100 como 1100100. Por supuesto, se necesita más memoria para almacenar el número 1100100 que 1. — el número asignado a un artículo cuando está en el mejor lugar. Diferencias como esa se vuelven significativas si almacenas, digamos, un millón de artículos.

Entonces, el equipo se dio cuenta de que si cambiaba continuamente elementos de la estructura de datos primaria a sus ubicaciones preferidas, podía reducir significativamente la memoria consumida por la estructura secundaria sin tener que aumentar los tiempos de consulta.

"Antes de este trabajo, nadie se había dado cuenta de que se podía comprimir aún más la estructura de datos moviendo la información", dijo Pagh. "Ésa fue la gran idea del artículo de Bender".

Los autores demostraron que su invención establecía un nuevo límite superior para las tablas hash más eficientes, lo que significa que era la mejor estructura de datos ideada hasta ahora en términos de eficiencia tanto de tiempo como de espacio. Pero seguía existiendo la posibilidad de que a alguien más le fuera aún mejor.

Obligado a triunfar

El año siguiente, un equipo liderado por Huacheng Yu, un informático de la Universidad de Princeton, intentó mejorar la tabla hash del equipo de Bender. "Trabajamos muy duro y no pudimos hacerlo", dijo Renfei Zhou, estudiante de la Universidad Tsinghua de Beijing y miembro del equipo de Yu. "Fue entonces cuando sospechamos que su límite superior era [también] un límite inferior", lo mejor que se puede lograr. "Cuando el límite superior es igual al límite inferior, el juego termina y tienes tu respuesta". No importa lo inteligente que seas, ninguna tabla hash puede hacerlo mejor.

El equipo de Yu empleó una estrategia novedosa para descubrir si esa corazonada era correcta calculando un límite inferior a partir de los primeros principios. En primer lugar, razonaron que para realizar una inserción o una eliminación, una tabla hash (o, en realidad, cualquier estructura de datos) debe acceder a la memoria de la computadora varias veces. Si pudieran calcular la cantidad mínima de veces necesarias para una tabla hash que aproveche el espacio, podrían multiplicarla por el tiempo requerido por acceso (una constante), lo que les daría un límite inferior en el tiempo de ejecución.

Pero si no sabían nada sobre la tabla hash (excepto que ocupaba poco espacio), ¿cómo podrían los investigadores calcular el número mínimo de veces necesarias para acceder a la memoria? Lo derivaron puramente de la teoría, utilizando un campo aparentemente no relacionado llamado teoría de la complejidad de la comunicación, que estudia cuántos bits se requieren para transmitir información entre dos partes. Finalmente, el equipo tuvo éxito: descubrieron cuántas veces una estructura de datos debe acceder a su memoria por operación.

Este fue su logro clave. Luego pudieron establecer un límite inferior en el tiempo de ejecución para cualquier tabla hash que aprovechara el espacio. Y vieron que coincidía exactamente con la tabla hash de Bender. “Pensamos [al principio] que se podría mejorar”, dijo Zhou. "Resultó que estábamos equivocados". Eso, a su vez, significó que el problema de Peterson finalmente se había resuelto.

Además de responder a la pregunta de hace décadas, dijo Kuszmaul, lo sorprendente de la prueba de Yu es su generalidad. "Su límite inferior se aplica a todas las estructuras de datos posibles, incluidas las que aún no se han inventado". Eso significa que ningún método de almacenamiento de datos podrá superar a la tabla hash de Bender en términos de memoria y velocidad.

Hashing hacia el futuro

A pesar de la eficiencia sin precedentes de la nueva tabla hash, es probable que nadie intente construirla en el corto plazo. Es demasiado complicado de construir. "Un algoritmo que es rápido en teoría no es necesariamente rápido en la práctica", dijo Zhou.

No es inusual que tales brechas entre teoría y práctica persistan durante mucho tiempo, dijo Kuszmaul, porque los teóricos tienden a ignorar factores constantes. El tiempo que lleva realizar una operación normalmente se multiplica por un número, una constante cuyo valor exacto puede ser irrelevante desde un punto de vista teórico. "Pero en la práctica, las constantes realmente importan", afirmó. "En el mundo real, un factor de 10 es el final del juego".

Las tablas hash reales todavía están mejorando de manera material, incluso si están muy por debajo del ideal teórico. Por ejemplo, una nueva tabla hash llamada IcebergHT, construido por Bender, Kuszmaul y otros, es mucho mejor que sus predecesores. Según Kuszmaul, es dos veces más rápida que la tabla hash más eficiente en cuanto a espacio disponible en la actualidad y utiliza tres veces menos espacio que la tabla hash más rápida.

Mitzenmacher espera que el resultado de 2023 pronto arroje otro tipo de beneficio: “Cada vez que se obtiene un nuevo límite inferior, especialmente uno que involucra algunas técnicas nuevas, siempre hay esperanza de que se puedan utilizar... para problemas relacionados”.

También está la satisfacción intelectual que surge al saber que se ha resuelto un problema difícil y de larga data, dijo el informático. Piotr Indyk del Instituto Tecnológico de Massachusetts. "Una vez que esté seguro de que ciertas estructuras de datos no se pueden mejorar, eso puede ayudar a centrar el esfuerzo de investigación". Finalmente, los investigadores de datos pueden desviar su atención del desafío de Peterson y centrarse en nuevos problemas de la informática teórica, de los que no faltan.