No obstante, el rendimiento de una tabla hash depende de su factor de carga (proporción entre elementos almacenados y capacidad total). Si la tabla se satura, aumentan las colisiones y el tiempo de búsqueda, lo que puede requerir ajustar su tamaño o rediseñar la función hash para mantener la eficacia. Por esto, su implementación óptima requiere equilibrar espacio en memoria y velocidad de operaciones.
Internet: las tablas Hash habían alcanzado su límite, pero...
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%.
Investigación antecedente
En 1985, Andrew Yao, premio Turing, estableció que en tablas hash con direccionamiento abierto, la búsqueda óptima de elementos o celdas vacías requería probar ubicaciones al azar ("hashing universal"). Además, demostró que en el peor caso —como buscar la última celda libre en una tabla 99% llena— el tiempo necesario sería proporcional a revisar unas 100 posiciones. Esta teoría se consideró válida durante cuatro décadas.
Sin embargo, en enero de 2025, Andrew Krapivin, un estudiante de posgrado de la Universidad de Cambridge, y sus colegas refutaron la hipótesis de Yao, demostrando que las tablas hash podían optimizarse más allá de lo previsto. Este hallazgo sorprendió a la comunidad científica, que no había anticipado tales mejoras en la eficiencia de estas estructuras.
El descubrimiento de Krapivin
A finales de 2021, Andrew Krapivin, entonces estudiante de la Universidad de Rutgers, descubrió un artículo sobre cómo reducir el tamaño de los punteros en memoria. Al retomar años después esa idea, entendió que podía optimizarlos aún más si mejoraba la organización de los datos asociados. Esto lo llevó a explorar tablas hash, donde accidentalmente desarrolló un nuevo tipo de estructura, más rápida y eficiente, que permitía localizar elementos con menos tiempo y recursos.
Al compartir su hallazgo con su profesor, Martin Farah-Colton (coautor del artículo original sobre punteros), este mostró escepticismo inicial, dada la exhaustiva investigación previa en tablas hash. Sin embargo, al involucrar a William Kuzmal, de Carnegie Mellon, se confirmó que Krapivin no solo había creado una tabla innovadora, sino que había refutado la hipótesis de Yao (vigente durante 40 años) sobre la necesidad de búsqueda aleatoria en tablas casi llenas. Curiosamente, Krapivin desconocía el trabajo de Yao, lo que quizás le permitió romper paradigmas establecidos.
Junto a Farah-Colton y Kuzmal (ahora como estudiante de posgrado en Cambridge), publicaron un método que logra tiempo constante de búsqueda, independientemente del nivel de llenado de la tabla, superando incluso el "hashing universal". Aunque su impacto inmediato es limitado, el avance podría optimizar procesos en Internet e inspirar nuevas investigaciones. De hecho, tras su publicación, surgió otro estudio proponiendo estrategias de búsqueda dinámicas basadas en la ocupación de celdas, evidenciando su influencia en el campo.
Más contenido en Urgente24:
Exitosa miniserie de Netflix regresó con segunda temporada
Finde XXL en AMBA: Los mejores Carnavales y pueblitos para pasear
Finde en Rosario: Carnaval, Cristian Castro y Dillom
Finde largo: Las mejores termas para descansar
Elon Musk sorprendió a todos con su anuncio
