Une conjecture de 40 ans sur les tables de hachage réfutée

Pendant quatre décennies, les informaticiens ont accepté la conjecture d'Andrew Yao de 1985 sur l'efficacité des recherches dans les tables de hachage. Cependant, Krapivin et son équipe ont développé une nouvelle table de hachage qui dépasse largement la limite du pire cas de Yao. Leur nouvel algorithme atteint un temps de requête et d'insertion beaucoup plus rapide et, étonnamment, le temps de requête moyen est constant, indépendamment du remplissage de la table. Ce résultat révolutionnaire réfute non seulement une croyance établie de longue date, mais ouvre également de nouvelles voies pour l'optimisation des tables de hachage.