Una investigación de pregrado que cambió los límites de búsqueda en tablas hash
(quantamagazine.org)- Andrew Krapivin, cuando era estudiante de pregrado en Rutgers, ideó una nueva tabla hash a partir del paper Tiny Pointers y mostró que era posible superar lo que se consideraban límites existentes de rendimiento en búsqueda e inserción
- En un paper de enero de 2025, Krapivin, Martín Farach-Colton y William Kuszmaul refutaron una conjetura de Yao de hace 40 años para cierta categoría de tablas hash
- La conjetura existente sostenía que, para x, que representa qué tan casi llena está la tabla, el peor tiempo de búsqueda e inserción no podía ser mejor que x, pero la nueva estructura logra un tiempo proporcional a (log x)²
- Los investigadores también mostraron que, en la categoría popular de tablas hash tratada por Yao, (log x)² es un límite óptimo que no puede reducirse más, y que en tablas hash no codiciosas el tiempo promedio de búsqueda puede llegar a ser constante, independiente de x
- Aunque no se traduzca de inmediato en aplicaciones, esto sienta una base teórica que reordena los límites de rendimiento de las tablas hash, una estructura de datos antigua, y abre la posibilidad de mejoras prácticas
Una nueva tabla hash que comenzó con Tiny Pointers
- Andrew Krapivin conoció el paper Tiny Pointers en el otoño de 2021, cuando era estudiante de pregrado en Rutgers University, y dos años después, al leerlo en detalle, se le ocurrió una forma de crear punteros más pequeños
- Como era necesario organizar mejor los datos a los que apuntarían esos punteros, las tablas hash, una forma común de almacenar datos, se convirtieron en el objeto de estudio
- Durante sus experimentos, Krapivin creó una nueva tabla hash que no dependía del sondeo uniforme (uniform probing) y descubrió que el tiempo y la cantidad de pasos para encontrar un elemento específico eran menores de lo esperado
- Martín Farach-Colton inicialmente dudó de este diseño, pero William Kuszmaul consideró que la estructura de Krapivin no era solo una tabla hash interesante, sino un resultado que derribaba una conjetura de hace 40 años
El problema de los límites de rendimiento de las tablas hash
- Una tabla hash es una estructura de datos para almacenar y acceder a datos, y básicamente soporta tres operaciones
- Consultar (query) un elemento
- Eliminar un elemento
- Insertar un elemento en un slot vacío
- Las primeras tablas hash se remontan a principios de la década de 1950, y desde entonces han sido una estructura de datos antigua que se ha seguido estudiando y usando en ciencias de la computación
- Los límites de velocidad de búsqueda o inserción suelen estar vinculados al tiempo que toma encontrar un espacio vacío en una tabla hash
- Qué tan llena está una tabla hash puede expresarse como una proporción total, pero al tratar con tablas casi llenas los investigadores usan el valor x
- Si x es 100, la tabla está llena en un 99%
- Si x es 1.000, la tabla está llena en un 99,9%
- En ciertas tablas hash comunes, se sabía que el tiempo esperado de inserción en el peor caso, como cuando se inserta un elemento en el último espacio vacío restante, era proporcional a x
La conjetura de Yao de 1985 y su refutación
- En un paper de 1985, Andrew Yao consideró que, en tablas hash con ciertas propiedades, la mejor forma de encontrar un elemento individual o un espacio vacío era el sondeo uniforme, que revisa posiciones posibles al azar
- Durante 40 años, se aceptó en gran medida como cierta la conjetura de que, en el peor caso —es decir, cuando se busca el último espacio vacío restante—, no se puede ser mejor que x
- Krapivin investigó temas relacionados con Tiny Pointers sin conocer la conjetura de Yao, y creó una nueva tabla hash que no dependía del sondeo uniforme
- El paper de enero de 2025 de Krapivin, Farach-Colton y Kuszmaul muestra que, en esta nueva tabla hash, el peor tiempo de búsqueda e inserción es proporcional a (log x)²
- Este resultado entra en conflicto directo con la conjetura de Yao, y los investigadores también demostraron que, en la categoría popular de tablas hash tratada por Yao, (log x)² es un límite óptimo que no puede reducirse más
Un resultado aún más sorprendente sobre el tiempo promedio de búsqueda
- En 1985, Yao no solo trató el peor tiempo de búsqueda, sino también el tiempo promedio entre todas las búsquedas posibles
- Demostró que, en tablas hash con ciertas propiedades, en especial las tablas hash codiciosas (greedy), donde un nuevo elemento debe colocarse en la primera posición posible, el tiempo promedio no puede ser mejor que log x
- Farach-Colton, Krapivin y Kuszmaul intentaron comprobar si el mismo límite se aplicaba también a las tablas hash no codiciosas, y mostraron mediante un contraejemplo que no era así
- En ese contraejemplo, una tabla hash no codiciosa tiene un tiempo promedio de búsqueda mucho mejor que log x y, en realidad, no depende en absoluto de x
- Que se pueda lograr un tiempo promedio de búsqueda constante sin importar qué tan llena esté la tabla hash fue un resultado inesperado incluso para los propios investigadores
Una actualización teórica para una estructura de datos antigua
- Alex Conway evalúa que las tablas hash son una de las estructuras de datos más antiguas y, aun así, siguen siendo una de las formas más eficientes de almacenar datos
- Guy Blelloch considera que este resultado es bello porque aborda y resuelve un problema clásico
- Sepehr Assadi evalúa que los investigadores no solo refutaron la conjetura de Yao, sino que también encontraron la mejor respuesta a su pregunta
- Conway considera que, aunque este resultado no derive de inmediato en aplicaciones, es importante entender mejor este tipo de estructuras de datos
- Este resultado, que reordena los límites teóricos de las tablas hash, sienta una base que más adelante podría traducirse en mejoras de rendimiento reales
1 comentarios
Comentarios de Hacker News
Parece que Krapivin logró este avance porque no conocía la conjetura de Yao, y que el desarrollador de Balatro también hizo una obra premiada porque no conocía bien los deckbuilders existentes
Da la impresión de que tal vez la mejor manera de abordar un problema sea no conocer, o ignorar, la mayoría de los intentos similares previos
El mundo actual está demasiado conectado, así que se ha vuelto raro ver ideas novedosas que no caigan en el marco mental de quienes vinieron antes; internet es maravilloso, pero es una pena que también tienda a homogeneizar el pensamiento
Normalmente, si ignoras los casos de éxito del pasado, vuelves a sembrar en un terreno que ya era estéril
Si lees los trabajos previos demasiado pronto, quedas atrapado en formas de pensar ya establecidas; si no los lees nunca, puedes perderte cosas importantes que no se te habrían ocurrido por tu cuenta
Incluso si tu enfoque resulta peor que el estado del arte existente, la comparación puede darte intuiciones valiosas sobre por qué el enfoque de vanguardia es mejor
Según una cita directa del desarrollador, la mayor influencia en Balatro fue Luck be a Landlord, y después de ver algunos videos de Northernlion jugándolo, le gustó la idea de un roguelike de puntuación con temática no fantástica y cambió el juego de cartas que estaba haciendo para convertirlo en un roguelike
A partir de ese momento se mantuvo deliberadamente alejado del género y dijo que quería equivocarse por su cuenta y explorar ingenuamente el espacio de diseño
Aunque a menudo comparan Balatro con Slay the Spire, dijo que cuando diseñó Balatro nunca había jugado ese título ni visto videos sobre él, y que lo conoció mucho después
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
“Pero nunca lo habría logrado sin la ayuda de todos”, replicó [Milo]
“Tal vez”, dijo Reason con solemnidad. “Pero tuviste el valor de intentarlo, y lo que puedes hacer suele depender de lo que estés dispuesto a intentar”.
El rey Azaz dijo: “Y por eso había algo muy importante sobre tu aventura que no podíamos decirte hasta que regresaras”.
“Lo recuerdo”, dijo Milo con entusiasmo. “Ahora díganmelo”.
“Era imposible”, dijo el rey mirando al Mathemagician
“Completamente imposible”, dijo el Mathemagician mirando al rey
“Entonces…”. dijo el insecto, mareado de repente
“Sí, exacto”, dijeron ambos al mismo tiempo. “Pero si te lo hubiéramos dicho entonces, quizá no habrías ido... y como ya has descubierto, si no sabes que es imposible, muchísimas cosas son posibles”.
— The Phantom Tollbooth (1961)
Como por varias razones reprobé esa clase y la volví a tomar, noté uno de sus hábitos
En una de las tareas de la segunda mitad de cada semestre, dentro de un conjunto de unas 30 preguntas, ponía una que en realidad era un problema abierto, y uno o dos días antes de la fecha límite mandaba una corrección diciendo “ah, fue un error”
Como siempre pasaba exactamente una vez, no parece que haya sido coincidencia
monort [0] compartió el enlace al video [1], y ayudó muchísimo.
Este es un resumen rápido basado en haber visto el video una vez; el nombre es funnel hashing.
La idea es dividir el arreglo en subarreglos exponencialmente más pequeños. El primer bloque es n/m, el segundo se va reduciendo como n/(m^2), y así hasta llegar a un solo elemento. Si los llamamos A0, A1, etc., entonces |A0| = n/m, |A1| = n/(m^2), y hay un total de k etapas.
Se intenta insertar c veces en A0, y si falla, se intenta c veces en A1. Si eso también falla, se sigue bajando por el “embudo” hasta encontrar un slot vacío.
Llaman \delta a la proporción de slots vacíos, pero no me queda claro si ese valor es un parámetro fijado al crear la tabla hash o si se actualiza dinámicamente. Si se toma c = log(1/d), k = log(1/d), la complejidad temporal en el peor caso queda en O(log^2(1/d)).
Entendí que este enfoque esquiva el resultado de Yao porque no es codicioso. El resultado de Yao aplica a políticas codiciosas de inserción y búsqueda, y el método de arriba no es codicioso porque va descendiendo en cadena por el embudo.
Debe de haber muchos detalles complicados, pero esa es más o menos la idea que entendí. Si lo interpreté totalmente mal, me gustaría que me corrigieran.
Me recuerda mucho a la idea de “Distinct Elements in Streams” de Chakraborty, Vinodchandran y Meel [2].
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing es “codicioso” y rompe la conjetura de Yao sobre mecanismos de hash codiciosos.
Elastic Hashing es “no codicioso” y ofrece un mejor tiempo amortizado que los algoritmos codiciosos.
No sé si el artículo está mal, si se entendió mal el paper, o si el autor del artículo señaló algo que no entendía bien.
Parece estar relacionado con la “última etapa especial para capturar unas cuantas claves” cerca del minuto 14:41 del video, pero si eso también tiene que ser de tamaño fijo, podría llenarse. ¿Qué habría que hacer en ese caso?
[Autopromoción descarada]: si te interesan las tablas hash, también vale la pena ver Dandelion Hashtable [0].
La usamos en nuestra base de datos de próxima generación, se presentó en HPDC'24 y actualmente es la tabla hash en memoria más rápida en uso real.
Mejora el direccionamiento cerrado con chaining de línea de caché limitada para manejar más de mil millones de solicitudes en memoria por segundo en servidores comunes.
[0] https://dandelion-datastore.com/#dlht
Presentación del inventor: https://www.youtube.com/watch?v=ArQNyOU1hyE
Se ve como uno de esos trucos de gestión de recursos a los que recurres cuando estás apretado por restricciones y te faltan recursos.
Dividir por prioridades es un enfoque común en asignación de recursos, y esto es una variante de eso.
Me pregunto cuántos otros “trucos de trinchera” que la gente ha usado en la práctica podrían darle la vuelta a cosas ampliamente aceptadas, aunque ni el propio inventor supiera que era algo importante. Algo como: “cuando tienes muchas entregas, normalmente descubres una forma ingeniosa de trazar la ruta más rápida…”.
Claro, reconocerlo, formalizarlo, trabajarlo y publicarlo como paper sí requiere un gran esfuerzo. No es para restarle mérito.
Ojalá los papers simplemente incluyeran una presentación en video.
Aun así, este enfoque también asigna más memoria mediante arreglos auxiliares, así que se siente un poco raro en qué sentido es mejor que simplemente sobreasignar para reducir la probabilidad de colisiones de claves y hacer menos malo el peor caso.
Hojeando el paper [1], la diferencia clave parece ser que el algoritmo de inserción de la tabla hash no llena de forma codiciosa el primer slot vacío que encuentra, sino que busca más allá.
Combinado con un orden de sondeo ingenioso, eso demuestra que puede encontrar slots vacíos de forma eficiente incluso cuando la tabla está muy llena.
En otras palabras, las inserciones se vuelven más lentas cuando la tabla hash está menos llena, pero se evita el peor escenario de estar buscando sin saber dónde quedaron los últimos pocos slots vacíos.
[1]: https://arxiv.org/pdf/2501.02305
Es un resultado teórico interesante, pero en la práctica esperaría que el “truco” actual de asignar una tabla más grande de lo necesario sea una mejor solución.
Por ejemplo, hashbrown de Rust deja intencionalmente libre 1/8 de la tabla, es decir, 12.5%, lo que usa un poco más de memoria pero hace que inserciones y búsquedas sean muy rápidas con alta probabilidad.
Ese enfoque aumenta el número promedio de posiciones sondeadas incluso cuando la tabla está menos llena.
Aun así, dentro de esta estrategia se coloca el elemento en el primer slot vacío que se ve.
“Saltarse slots” parece estar relacionado con saltar hacia adelante en el orden del hash.
¿Alguien tiene una implementación simple de ‘Tiny pointers’? Mi cabeza prefiere ver primero código o pseudocódigo antes que demostraciones.
Qué bueno. Siempre me pregunté si habría una forma de containerizar las tablas de esta manera
Una tabla normal se parece a un carguero granelero donde meten todo junto. Si se pudiera organizar mejor, como un buque portacontenedores, parecería posible cargar mucho más de forma más eficiente y descargarlo más rápido
Convierte una fila de la tabla en algo como una cadena o JSON, y aplica base16 a esa variable para obtener la cadena base16 de esos datos
Crea una tabla hash y asigna un valor clave para esa cadena base16; así tendrás un contenedor con los datos
Ahora solo hay que decodificar la cadena hexadecimal para obtener datos base32
Las propiedades teóricas de las tablas hash siempre me parecieron impresionantes, casi mágicas, y este resultado las extiende aún más
Lo que me resultaba extraño era cómo una tabla hash podía ser mucho mejor que un árbol, que intuitivamente parecía la forma más eficiente de almacenar datos
Lo que entendí es que la teoría de tablas hash trabaja con un conjunto de objetos de tamaño fijo. Para ese conjunto fijo se construye una función hash, y se usa como si fuera un índice de vector para almacenarlo en un vector preasignado. De ahí sale la receta para tener inserción, borrado y consulta cercanos a O(1). En cambio, muchas estructuras de árbol no asumen un tamaño determinado
El problema es que hay que fijar el tamaño por adelantado, y cuando el vector está casi lleno procesos como la inserción pueden volverse lentos
Por lo que hojeé del artículo, este resultado parece resolver esa parte lenta y permitir inserciones rápidas incluso en tablas casi llenas
Es interesante e ingenioso, pero no parece un gran avance práctico. En la práctica, en vez de pensar cómo llenar la tabla de forma ingeniosa, parecería suficiente aumentar el tamaño asumido
Lo escribo para comprobar si lo entendí bien, así que si está mal, corríjanme
En las inserciones donde ocurre un redimensionamiento, toma un tiempo mucho mayor, lineal respecto al tamaño de la tabla, pero ese tiempo se amortiza sobre todas las inserciones ya realizadas
Si cada vez que la tabla empieza a llenarse demasiado la haces crecer lo suficiente, la frecuencia de esos eventos baja cada vez más, así que en promedio sigue siendo tiempo constante
En el mundo funcional, probablemente los árboles sigan siendo más adecuados
No tuve tiempo de entender completamente el paper, pero afirman que así la inserción es consistentemente rápida. Hasta el 75% de la capacidad total me hace sentido, pero no sé si tienen otro modo cuando todas las filas llegan al 75%
También afirman que la consulta es rápida, pero no alcancé a leer lo suficiente como para entender cómo funciona ni por qué es rápida
Si una tabla hash casi llena sigue funcionando bien, hay muchas situaciones donde eso sería realmente útil. No siempre puedes cambiarle el tamaño a un programa mientras está corriendo, y en algunos entornos la memoria importa muchísimo
Aun así, quiero ver la implementación y probarla yo mismo. No estoy seguro de si en el caso general esto realmente “vale la pena”
También es probable que no tenga buena eficiencia de caché. Eso pasa con la mayoría de las tablas hash, pero cuando lees con sondeo lineal en una tabla bastante llena hay una excepción: puedes ir comprobando memoria de forma contigua
Todavía no está claro si vale la pena desde el punto de vista del rendimiento, pero es una idea nueva interesante y me gustaría entenderla por completo
No entiendo la parte que dice: “En esta nueva tabla hash, el tiempo necesario para la peor consulta e inserción es proporcional a (log x)2, y es mucho más rápido que x”, pero aun así “el resultado del equipo quizá no lleve a aplicaciones inmediatas”
¿Por qué no llevaría a aplicaciones inmediatas? ¿Significa que, al analizar casos de uso reales, puede ajustarse mejor una implementación hash mediante enfoques prácticos que con una aproximación puramente matemática?
A veces el dataset tendría que ser irrealmente grande para ver la mejora de velocidad
Entonces x no llega a ser mayor que 4, así que mejorar O(x) a O((log x)^2) no significa mucho cuando x es tan pequeño
En algunas aplicaciones especiales con restricciones de memoria sí se pondría x más alto, pero personalmente nunca me encontré con esos casos
Siempre que se necesitó un factor de carga muy alto, por ejemplo por encima del 90%, cuckoo hashing fue suficiente, y por debajo de 70~80% el sondeo lineal fue muy rápido y suficientemente bueno
El nuevo resultado también tiene el costo de hacer más lenta la inserción en los “buenos casos”
No parece haber nada en el paper que vaya a impactar el trabajo práctico
Este resultado parece importar solo cuando la tabla hash está casi llena
Entonces, ¿no bastaría con hacer la tabla un 10% más grande o, si puede redimensionarse, hacer el resize antes?
Cuando la probabilidad de colisiones hash se vuelve demasiado alta, ajustan su tamaño por sí solas
Si la tabla se llena demasiado, simplemente asignas el doble de memoria o algún múltiplo fijo adicional y copias los elementos existentes
La mayoría de las tablas con sondeo no lineal, como cuckoo hashing, salen perdiendo por el hecho de que la RAM en realidad no es nada “aleatoria”
¿Alguien conoce un repositorio de GitHub con esta implementación?