Des recherches d’un étudiant de licence renversent les limites de recherche des tables de hachage
(quantamagazine.org)- Andrew Krapivin, alors étudiant de licence à Rutgers, a conçu une nouvelle table de hachage à partir de l’article Tiny Pointers et a montré qu’il était possible de dépasser ce qui était considéré comme les limites existantes des performances de recherche et d’insertion
- Dans un article publié en janvier 2025, Krapivin, Martín Farach-Colton et William Kuszmaul réfutent la conjecture vieille de 40 ans de Yao pour une certaine catégorie de tables de hachage
- La conjecture existante estimait que, pour x, qui représente le degré auquel une table est presque pleine, le temps de recherche et d’insertion dans le pire cas ne pouvait pas faire mieux que x ; la nouvelle structure atteint un temps proportionnel à (log x)²
- Les chercheurs ont aussi montré que, dans la catégorie populaire de tables de hachage étudiée par Yao, (log x)² est une borne optimale qu’on ne peut pas abaisser davantage, et que les tables de hachage non gloutonnes peuvent même offrir un temps de recherche moyen constant, indépendant de x
- Même si cela ne débouche pas immédiatement sur des applications, ce résultat fournit une base théorique qui redéfinit les limites de performance des tables de hachage, une structure de données ancienne, et ouvre la voie à de possibles améliorations pratiques
Une nouvelle table de hachage née de Tiny Pointers
- À l’automne 2021, alors qu’il était étudiant de licence à Rutgers University, Andrew Krapivin a découvert l’article Tiny Pointers et, en le lisant en détail deux ans plus tard, a eu l’idée d’une manière de créer des pointeurs plus petits
- Comme il fallait mieux organiser les données vers lesquelles pointaient ces pointeurs, les tables de hachage, un mode courant de stockage des données, sont devenues l’objet de ses recherches
- Au cours de ses expériences, Krapivin a créé une nouvelle table de hachage ne reposant pas sur le sondage uniforme (uniform probing) et a constaté que le temps et le nombre d’étapes nécessaires pour trouver un élément donné étaient inférieurs à ce qui était attendu
- Martín Farach-Colton s’est d’abord montré sceptique face à cette conception, mais William Kuszmaul a estimé que la structure de Krapivin n’était pas seulement une table de hachage intéressante : elle faisait tomber une conjecture vieille de 40 ans
Le problème des limites de performance des tables de hachage
- Une table de hachage est une structure de données qui stocke les données et permet d’y accéder ; elle prend essentiellement en charge trois opérations
- Rechercher (query) un élément
- Supprimer un élément
- Insérer un élément dans un emplacement vide
- Les premières tables de hachage remontent au début des années 1950 et, depuis, cette structure de données ancienne n’a cessé d’être étudiée et utilisée en informatique
- Les limites de vitesse de la recherche ou de l’insertion sont généralement liées au temps nécessaire pour trouver un emplacement vide dans une table de hachage
- Le taux de remplissage d’une table de hachage peut s’exprimer sous forme de proportion globale, mais les chercheurs utilisent la valeur x lorsqu’ils traitent des tables presque pleines
- Si x vaut 100, la table est remplie à 99 %
- Si x vaut 1 000, la table est remplie à 99,9 %
- Pour certaines tables de hachage courantes, on savait que le temps d’insertion espéré dans le pire cas, par exemple lorsqu’il faut placer un élément dans le dernier emplacement vide restant, est proportionnel à x
La conjecture de Yao de 1985 et sa réfutation
- Dans un article de 1985, Andrew Yao considérait que, pour les tables de hachage dotées de certaines propriétés, la meilleure façon de trouver un élément ou un emplacement vide était le sondage uniforme, qui parcourt au hasard les positions possibles
- Dans le pire des cas, c’est-à-dire lorsqu’il faut trouver le dernier emplacement vide restant, la conjecture selon laquelle il était impossible de faire mieux que x a été largement tenue pour vraie pendant 40 ans
- Krapivin a poursuivi ses recherches liées à Tiny Pointers sans connaître la conjecture de Yao et a créé une nouvelle table de hachage qui ne dépend pas du sondage uniforme
- L’article de janvier 2025 de Krapivin, Farach-Colton et Kuszmaul montre que, dans cette nouvelle table de hachage, le temps de recherche et d’insertion dans le pire cas est proportionnel à (log x)²
- Ce résultat contredit directement la conjecture de Yao, et les chercheurs ont également prouvé que, dans la catégorie populaire de tables de hachage étudiée par Yao, (log x)² est une borne optimale qu’on ne peut pas abaisser davantage
Un résultat encore plus surprenant sur le temps de recherche moyen
- En 1985, Yao ne s’est pas seulement intéressé au temps de recherche dans le pire cas, mais aussi au temps moyen sur l’ensemble des recherches possibles
- Pour les tables de hachage dotées de certaines propriétés, en particulier les tables de hachage gloutonnes (greedy), où un nouvel élément doit être placé au premier emplacement possible, il a prouvé que le temps moyen ne pouvait pas faire mieux que log x
- Farach-Colton, Krapivin et Kuszmaul ont voulu vérifier si la même limite s’appliquait aussi aux tables de hachage non gloutonnes, et ont montré par un contre-exemple que ce n’était pas le cas
- Cette table de hachage non gloutonne, qui sert de contre-exemple, offre un temps de recherche moyen bien meilleur que log x et, en pratique, ne dépend pas du tout de x
- Le fait de pouvoir atteindre un temps de recherche moyen constant, indépendamment du niveau de remplissage de la table de hachage, a été un résultat inattendu même pour les chercheurs
Une mise à jour théorique d’une ancienne structure de données
- Alex Conway estime que les tables de hachage font partie des structures de données les plus anciennes, tout en restant l’une des méthodes les plus efficaces pour stocker des données
- Guy Blelloch voit dans ce résultat quelque chose de beau, parce qu’il aborde et résout un problème classique
- Sepehr Assadi estime que les chercheurs n’ont pas seulement réfuté la conjecture de Yao, mais ont aussi trouvé la meilleure réponse à sa question
- Conway considère que, même si ce résultat ne débouche pas immédiatement sur des applications, il est important de mieux comprendre ce type de structure de données
- En redéfinissant les limites théoriques des tables de hachage, ce résultat fournit une base qui pourrait mener plus tard à de réelles améliorations de performance
1 commentaires
Avis sur Hacker News
Krapivin a réalisé cette percée parce qu’il ne connaissait pas la conjecture de Yao, et je pense que le développeur de Balatro a aussi créé un jeu primé parce qu’il connaissait mal les deck builders existants
Je me dis que la meilleure manière d’aborder un problème est peut-être de ne pas connaître, ou d’ignorer, la plupart des tentatives similaires précédentes
Le monde d’aujourd’hui est tellement connecté qu’il est devenu rare de voir une nouveauté qui ne tombe pas dans les cadres de pensée de ceux qui l’ont précédée ; Internet est formidable, mais il est dommage qu’il homogénéise aussi la pensée
Le plus souvent, si l’on ignore les réussites du passé, on finit par ressemer un terrain qui s’était déjà révélé stérile
Si on lit les travaux antérieurs trop tôt, on se retrouve enfermé dans les modes de pensée existants ; si on ne les lit pas du tout, on passe à côté de choses importantes auxquelles on n’aurait pas pensé soi-même
Même si votre approche est moins bonne que l’état de l’art, la comparaison peut vous apporter des intuitions importantes sur les raisons pour lesquelles l’approche de pointe est meilleure
D’après une citation directe du développeur, la plus grande influence de Balatro a été Luck be a Landlord ; après avoir regardé quelques vidéos de Northernlion y jouant, il a apprécié le concept d’un roguelike d’attaque de score sur un thème non fantasy, et a transformé le jeu de cartes qu’il développait alors en roguelike
À partir de ce moment-là, il a volontairement pris ses distances avec le genre, voulant explorer naïvement l’espace de conception en commettant ses propres erreurs
Il entend souvent des comparaisons avec Slay the Spire, mais lorsqu’il concevait Balatro, il n’avait jamais joué à ce jeu ni regardé de vidéos à son sujet, et ne l’a découvert que beaucoup plus tard
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
« Mais je n’aurais jamais pu y arriver sans l’aide de tout le monde », protesta [Milo]
« Peut-être bien », dit Reason d’un ton solennel. « Mais tu as eu le courage d’essayer, et ce que tu peux faire dépend généralement de ce que tu as l’intention de faire. »
King Azaz dit : « C’est pourquoi il y avait une chose très importante, dans ton aventure, que nous ne pouvions pas te dire avant ton retour. »
« Je m’en souviens », dit Milo avec empressement. « Dites-la-moi maintenant. »
« C’était impossible », dit le roi en regardant le Mathemagician
« Complètement impossible », dit le Mathemagician en regardant le roi
« Alors… », dit brusquement l’insecte, pris de vertige
« Oui, exactement », dirent-ils ensemble. « Mais si nous te l’avions dit à ce moment-là, tu n’y serais peut-être pas allé… et comme tu l’as découvert, tant qu’on ne sait pas que c’est impossible, on peut accomplir énormément de choses. »
— The Phantom Tollbooth (1961)
Ayant eu pas mal de soucis, j’ai échoué à ce cours et je l’ai repris, ce qui m’a fait remarquer une habitude
Chaque semestre, dans l’un des devoirs de la seconde moitié du cours, parmi une série d’environ 30 questions, il en posait une qui était en réalité un problème ouvert, puis envoyait une version corrigée un jour ou deux avant la date limite en disant : « Ah, c’était une erreur »
Comme cela arrivait toujours exactement une fois, je doute que ce soit un hasard
monort [0] a donné un lien vers la vidéo [1], ce qui a beaucoup aidé
Voici un résumé rapide après un visionnage : le nom est Funnel Hashing
L’idée consiste à diviser le tableau en sous-tableaux de taille exponentiellement décroissante. Le premier bloc fait n/m, le deuxième n/(m^2), et ainsi de suite jusqu’à un seul élément. Si on les appelle A0, A1, etc., alors |A0| = n/m, |A1| = n/(m^2), avec k étapes au total
On tente d’insérer c fois dans A0 ; en cas d’échec, on tente c fois dans A1. Si cela échoue aussi, on descend le long du « funnel » jusqu’à trouver un slot libre
\delta désigne la proportion de slots libres, mais je ne sais pas très bien s’il s’agit d’un paramètre fixé à la création de la table de hachage ou d’une valeur mise à jour dynamiquement. En posant c = log(1/d), k = log(1/d), la complexité temporelle dans le pire cas devient O(log^2(1/d))
J’ai compris que cette méthode contourne le résultat de Yao parce qu’elle n’est pas gloutonne. Le résultat de Yao vaut pour des politiques d’insertion et de recherche gloutonnes, tandis que la méthode ci-dessus descend en cascade le long du funnel, donc elle est non gloutonne
Il y a sûrement beaucoup de détails délicats, mais c’est à peu près l’idée telle que je l’ai comprise. Si je suis complètement à côté de la plaque, j’aimerais qu’on me le dise
Cela me rappelle beaucoup l’idée de « Distinct Elements in Streams » de Chakraborty, Vinodchandran et 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 est « glouton » et réfute la conjecture de Yao sur les mécanismes de hachage gloutons
Elastic Hashing est « non glouton » et offre un meilleur temps amorti que les algorithmes gloutons
Je ne sais pas si c’est l’article qui se trompe ou si c’est la compréhension du papier qui est mauvaise, mais je me demande si l’auteur de l’article a relevé un point qu’il ne maîtrise pas
Cela semble lié à l’« étape finale spéciale pour capturer quelques clés » vers 14:41 dans la vidéo, mais si elle aussi doit être de taille fixe, elle peut se remplir. Que faut-il faire dans ce cas ?
[auto-promo éhontée] : si les tables de hachage vous intéressent, Dandelion Hashtable [0] vaut aussi le détour
Nous l’utilisons dans notre base de données de nouvelle génération, elle a été présentée à HPDC'24, et c’est actuellement la table de hachage en mémoire la plus rapide en usage réel
Elle améliore l’adressage fermé avec un chaînage limité par ligne de cache, et traite plus d’un milliard de requêtes en mémoire par seconde sur des serveurs ordinaires
[0] https://dandelion-datastore.com/#dlht
Présentation de l’inventeur : https://www.youtube.com/watch?v=ArQNyOU1hyE
Cela ressemble à l’une de ces astuces de gestion des ressources qu’on utilise quand on est acculé par les contraintes et qu’on manque de ressources
Découper par priorité est une approche courante en allocation de ressources, et ceci en est une variante
Je me demande combien d’autres « astuces de tranchée » que les gens ont utilisées sur le terrain, sans que même leur inventeur sache que c’était important, pourraient renverser des idées largement admises. Du genre : « quand il y a beaucoup de choses à livrer, j’ai trouvé une méthode astucieuse pour tracer généralement l’itinéraire le plus rapide… »
Bien sûr, reconnaître cela, le formaliser, travailler dessus et en faire un article demande beaucoup d’efforts. Je ne cherche pas à minimiser ce mérite
J’aimerais que les articles incluent tout simplement une présentation vidéo
Cela dit, cette approche alloue elle aussi davantage de mémoire via des tableaux auxiliaires, et il me semble un peu étrange qu’elle soit meilleure que le simple fait de surallouer pour réduire la probabilité de collisions de clés et rendre le pire cas moins mauvais
En survolant le papier [1], la différence clé semble être que l’algorithme d’insertion dans la table de hachage ne remplit pas gloutonnement le premier slot libre trouvé, mais cherche plus loin
Combiné à un ordre de sondage malin, cela permet de prouver qu’il trouve efficacement des slots libres même lorsque la table est très pleine
Autrement dit, les insertions sont plus lentes lorsque la table est moins remplie, mais on évite le pire cas où l’on cherche sans savoir où se trouvent les derniers slots libres restants
[1]: https://arxiv.org/pdf/2501.02305
C’est un résultat théorique intéressant, mais en pratique je m’attends à ce que l’« astuce » actuelle consistant à allouer une table plus grande que nécessaire soit une meilleure solution
Par exemple, hashbrown de Rust laisse volontairement 1/8 de la table, soit 12,5 %, vide : cela utilise un peu plus de mémoire, mais rend les insertions et les recherches très rapides avec une forte probabilité
Cette méthode augmente aussi le nombre moyen de positions sondées lorsque la table est moins remplie
Malgré tout, dans cette stratégie, l’élément est placé dans le premier slot libre rencontré
Le « saut de slots » est lié au fait de sauter vers l’avant dans l’ordre de hachage
Quelqu’un a-t-il une implémentation simple de « Tiny pointers » ? Mon cerveau préfère voir du code ou du pseudocode avant les preuves
Génial. Je me suis toujours demandé s’il y aurait un moyen de conteneuriser des tables de cette façon
Une table ordinaire ressemble à un vraquier où l’on entasse tout. Si on pouvait l’organiser mieux, comme un porte-conteneurs, on pourrait sans doute y charger bien plus de choses plus efficacement, et les décharger plus vite aussi
Il suffit de convertir les lignes de la table en chaîne ou en quelque chose comme du JSON, puis d’appliquer base16 à cette variable pour obtenir la chaîne base16 de ces données
Créez une table de hachage et définissez une valeur de clé pour cette chaîne base16, et vous obtenez un conteneur avec les données
Il ne reste plus qu’à décoder la chaîne hexadécimale pour obtenir les données base32
Les propriétés théoriques des tables de hachage m’ont toujours paru impressionnantes, presque magiques, et ce résultat les étend encore
Ce qui me semblait étrange, intuitivement, c’est comment les tables de hachage peuvent être tellement meilleures que les arbres, qui donnaient l’impression d’être la manière la plus efficace de stocker des données
Ce que j’ai compris, c’est que la théorie des tables de hachage traite d’un ensemble d’objets de taille fixe. Pour cet ensemble fixe, on construit une fonction de hachage, qu’on utilise comme un index de vecteur pour stocker les objets dans un vecteur préalloué. C’est ce qui permet d’obtenir une recette pour des insertions, suppressions et recherches proches de O(1). En revanche, les différentes structures d’arbres ne supposent pas une taille particulière
Le problème est qu’il faut fixer la taille à l’avance, et que lorsque le vecteur est presque plein, des opérations comme l’insertion peuvent ralentir
En survolant l’article, ce résultat semble résoudre cette partie qui ralentit, et permettre des insertions rapides même dans des tables presque pleines
C’est intéressant et astucieux, mais je doute que ce soit une grande avancée pratique. En pratique, plutôt que de réfléchir à une façon intelligente de remplir une table, il suffit selon moi d’augmenter la taille supposée
J’écris ça pour vérifier si ma compréhension est correcte, donc n’hésitez pas à me corriger si je me trompe
Lors d’une insertion qui déclenche un redimensionnement, le temps pris est bien plus important, linéaire dans la taille de la table, mais ce coût est amorti sur toutes les insertions déjà effectuées
Si on agrandit suffisamment la table chaque fois qu’elle commence à être trop pleine, ces événements deviennent de moins en moins fréquents, si bien qu’en moyenne on reste en temps constant
Dans le monde fonctionnel, les arbres restent probablement plus adaptés
Je n’ai pas eu le temps de comprendre complètement l’article, mais il affirme que cette méthode rend les insertions systématiquement rapides. Je comprends jusqu’aux 75 % de la capacité totale, mais je ne sais pas s’il existe un autre mode lorsque toutes les lignes atteignent 75 %
Il affirme aussi que les recherches sont rapides, mais je n’ai pas assez lu pour comprendre comment elles fonctionnent ni pourquoi elles sont rapides
Il y a beaucoup de situations où une table de hachage presque pleine qui fonctionne quand même serait vraiment utile. On ne peut pas toujours redimensionner pendant l’exécution d’un programme, et dans certains environnements la mémoire est cruciale
Cela dit, j’aimerais voir l’implémentation et la manipuler moi-même. Je ne suis pas sûr que, dans le cas général, ça en « vaille la peine »
L’efficacité du cache risque aussi d’être mauvaise. C’est le cas pour la plupart des tables de hachage, à l’exception notable des lectures par sondage linéaire dans une table assez remplie, où l’on peut récupérer et vérifier des éléments contigus en mémoire
Il n’est pas encore clair si cela vaut le coup du point de vue des performances, mais c’est une nouvelle idée intéressante que j’aimerais comprendre complètement
Je ne comprends pas le passage qui dit que « dans cette nouvelle table de hachage, le temps nécessaire aux requêtes et aux insertions dans le pire cas est proportionnel à (log x)2, ce qui est bien plus rapide que x », tout en ajoutant que « le résultat de l’équipe ne débouchera peut-être pas sur des applications immédiates »
Pourquoi n’y aurait-il pas d’applications immédiates ? Est-ce que cela signifie que l’analyse des cas d’usage réels permettrait de mieux ajuster les implémentations de hachage qu’une approche purement mathématique ?
Il faut parfois des jeux de données irréalistement grands pour observer une accélération
Dans ce cas, x ne dépasse pas 4, donc améliorer O(x) en O((log x)^2) n’a pas de sens quand x est aussi petit
Dans certaines applications spécialisées avec des contraintes de mémoire, on fixerait x plus haut, mais personnellement je n’ai jamais rencontré ce cas
Chaque fois qu’un facteur de charge très élevé était nécessaire, par exemple au-dessus de 90 %, le hachage cuckoo suffisait, et à 70–80 % ou moins, le sondage linéaire était très rapide et largement suffisant
Le nouveau résultat a aussi pour coût de ralentir les insertions dans les « bons cas »
Je ne vois rien dans l’article qui semble susceptible d’avoir un impact sur la pratique
Ce résultat ne semble important que lorsque la table de hachage est presque pleine
Dans ce cas, ne suffit-il pas de choisir une table 10 % plus grande, ou de la redimensionner plus tôt si le redimensionnement est possible ?
Lorsque la probabilité de collisions de hachage devient trop élevée, elles se redimensionnent d’elles-mêmes
Quand la table devient trop pleine, on alloue simplement deux fois plus de mémoire, ou un multiple fixe, puis on copie les éléments existants
La plupart des tables à sondage non linéaire, par exemple le hachage cuckoo, sont pénalisées par le fait que la RAM n’est pas du tout « aléatoire »
Quelqu’un connaît-il le dépôt GitHub de cette implémentation ?