Estudiante desarrolla innovadora tabla hash que desafía teoría de 40 años

Andrew Krapivin, un estudiante de pregrado de la Universidad de Rutgers, ha logrado un avance significativo en el campo de la ciencia de datos al desarrollar un nuevo tipo de tabla hash que funciona más rápido de lo esperado. Su descubrimiento, realizado mientras trabajaba en un proyecto sobre ‘punteros diminutos’, ha refutado una conjetura de 40 años propuesta por el científico informático Andrew Yao. Krapivin demostró que, para ciertas tablas hash, el tiempo requerido para las peores consultas e inserciones es proporcional a (log x)², lo que es significativamente más rápido que x, como se creía anteriormente. Este hallazgo no solo contradice la conjetura de Yao, sino que también establece un nuevo límite óptimo para una clase popular de tablas hash. Además, Krapivin y sus colaboradores descubrieron un resultado aún más sorprendente: una tabla hash no codiciosa con un tiempo de consulta promedio constante, independiente de qué tan llena esté la tabla. Estos descubrimientos tienen el potencial de mejorar significativamente la eficiencia de las estructuras de datos fundamentales en informática, aunque las aplicaciones prácticas inmediatas aún no están claras4.