Un étudiant de premier cycle a brisé une croyance vieille de 40 ans en l’informatique. Depuis 1985, on croyait que les tables de hachage, lorsqu’elles étaient presque pleines, devaient vérifier de nombreux endroits pour trouver ou ajouter des données. Andrew Krapivin a découvert une nouvelle façon d’organiser les données à l’intérieur d’une table de hachage qui évite ce ralentissement. Au lieu de vérifier les créneaux au hasard ou dans l’ordre, sa méthode utilise une structure plus efficace pour guider la recherche. Cela réduit le temps le plus défavorable de O(n) à (log n)² pas, même lorsque la table est presque pleine.