Il y a environ 70 ans, un ingénieur chez IBM nommé Hans Peter Luhn a discrètement changé le cours de l'informatique. Luhn détenait déjà plusieurs brevets, dont un pour un appareil capable de mesurer le nombre de fils d'un tissu et un autre pour un guide déterminant les boissons mélangées que vous pouviez préparer à partir des ingrédients de votre cuisine. Mais dans un article interne d'IBM de 1953, il proposait une nouvelle technique de stockage et de récupération d'informations qui est désormais intégrée à presque tous les systèmes informatiques : la table de hachage.

Les tables de hachage constituent une classe majeure de structures de données. Ils offrent une méthode particulièrement pratique pour accéder et modifier les informations contenues dans des bases de données volumineuses. Mais cette technologie s’accompagne d’un compromis inévitable.

Dans un 1957 papier publié au Revue IBM de recherche et développement, W. Wesley Peterson a identifié le principal défi technique que posent les tables de hachage : elles doivent être rapides, ce qui signifie qu'elles peuvent récupérer rapidement les informations nécessaires. Mais ils doivent également être compacts et utiliser le moins de mémoire possible. Ces deux objectifs sont fondamentalement contradictoires. L'accès et la modification d'une base de données peuvent être effectués plus rapidement lorsque la table de hachage dispose de plus de mémoire ; et les opérations deviennent plus lentes dans les tables de hachage qui utilisent moins d'espace. Depuis que Peterson a lancé ce défi, les chercheurs tentent de trouver le meilleur équilibre entre le temps et l’espace.

Les informaticiens ont maintenant prouvé mathématiquement qu’ils avaient trouvé le compromis optimal. La solution est venue d'un paire de récents papiers qui se complétaient. "Ces articles résolvent la question ouverte de longue date sur les meilleurs compromis spatio-temporels possibles, produisant des résultats profondément surprenants qui, je l'espère, auront un impact significatif pendant de nombreuses années à venir", a déclaré Michael Mitzenmacher, un informaticien de l'Université Harvard qui n'a participé à aucune des deux études.

"Je dirais certainement que c'est un gros problème", a ajouté Rasmus Pagh, informaticien à l'Université de Copenhague. « De nombreuses personnes ont travaillé sur ce problème, essayant de voir dans quelle mesure il était possible de réduire l'espace tout en réalisant des opérations plus rapides. C’est celui que j’aurais adoré résoudre.

En faire un hachage

Les tables de hachage comptent aujourd’hui parmi les structures de données les plus anciennes, les plus simples, les plus rapides et les plus largement utilisées. Ils sont conçus pour effectuer trois opérations de base : les insertions, qui ajoutent de nouveaux éléments à la base de données ; les requêtes, qui accèdent à un élément ou vérifient s'il existe ; et suppressions. Une table de hachage peut être éphémère (n'exister que tant qu'un programme particulier s'exécute) ou elle peut constituer un élément permanent du système d'exploitation de votre ordinateur. Un navigateur Web tel que Chrome ou Safari peut avoir plusieurs tables de hachage intégrées destinées à suivre différents types de données.

Les entrées dans une table de hachage sont stockées par paires, l'élément (l'information elle-même) étant connecté à une clé qui identifie l'information. Branchez une clé dans l'algorithme de requête d'une table de hachage et cela vous amène directement à l'élément. Cela peut ne pas paraître si extraordinaire, mais pour d’énormes bases de données, cela peut représenter un gain de temps considérable.

Pour prendre un exemple extrêmement simplifié, considérons l'Oxford English Dictionary, qui propose des définitions pour plus de 600,000 XNUMX mots. Si une édition numérique repose sur une table de hachage, vous pouvez simplement utiliser un mot donné comme clé et passer directement à la définition. Sans table de hachage, le dictionnaire s'appuierait probablement sur un mécanisme de recherche beaucoup plus lent, utilisant un processus d'élimination pour finalement converger vers la définition demandée. Et tandis qu'une table de hachage peut trouver n'importe quel mot dans un laps de temps constant (généralement une infime fraction de seconde), le temps de recherche pour d'autres méthodes peut augmenter à mesure que le nombre de mots dans le dictionnaire augmente. Une table de hachage offre également un autre avantage : elle peut maintenir le dictionnaire dynamique, ce qui facilite l'insertion de nouveaux mots et la suppression de mots obsolètes.

Les chercheurs ont passé des décennies à créer des tables de hachage qui tentent d'optimiser la vitesse et de minimiser la mémoire. Au XXe siècle, les solutions tendaient à offrir des gains significatifs sur un seul aspect, le temps ou l’espace. Puis en 20, des chercheurs montré qu'il était théoriquement possible de faire un saut d'efficacité majeur simultanément dans le temps et dans l'espace. Il faudra cependant encore deux décennies aux chercheurs pour trouver l’équilibre idéal entre les deux.

Le brassage des données

La première étape majeure vers cet objectif a eu lieu en 2022 à un moment donné. grande conférence informatique à Rome. Là, une équipe a proposé une table de hachage dotée de nouvelles fonctionnalités qui pourraient offrir la meilleure combinaison d’efficacité temporelle et spatiale jamais conçue. Le premier auteur de l'article (classé par ordre alphabétique) était Michael Bender de l'Université de Stony Brook, il est donc communément appelé Bender et al. table de hachage. Même si l'équipe n'a pas essayé de construire une table de hachage fonctionnelle, elle a prouvé qu'elle pouvait, en principe, être construite avec les fonctionnalités décrites.

Pour évaluer la table de hachage qu'ils ont imaginée, le groupe a produit une courbe de compromis : un graphique qui trace le temps par opération (insertion ou suppression) sur un axe et l'espace occupé par la mémoire sur l'autre. Mais ce graphique définit l'espace d'une manière particulière : en raison de la façon dont elles sont construites, les tables de hachage ont besoin de plus de mémoire que le strict minimum requis pour stocker un ensemble d'éléments donné. Les informaticiens appellent cet espace supplémentaire des « bits gaspillés », même s'ils ne sont pas vraiment gaspillés et sont, dans une certaine mesure, nécessaires. L'axe spatial sur une courbe de compromis mesure le nombre de bits gaspillés par clé.

En analysant une courbe de compromis, les chercheurs peuvent déterminer le temps le plus rapide possible pour une table de hachage qui utilise une quantité d'espace donnée. Ils peuvent également inverser la question pour déterminer l’espace le plus petit possible pour une durée d’opération donnée. Habituellement, un petit changement dans une variable entraînera un petit changement dans l'autre, a déclaré William Kuszmaul, informaticien théorique à Harvard et co-auteur de l'article de 2022. "Si vous doublez le temps, vous réduirez peut-être de moitié le nombre de bits gaspillés par clé."

Mais ce n’est pas le cas de la table de hachage qu’ils ont conçue. "Si vous augmentez un peu le temps, les bits gaspillés par clé diminuent de façon exponentielle", a déclaré Kuszmaul. La courbe des compromis était si abrupte qu’elle était littéralement hors du commun.

L'équipe a construit sa table de hachage en deux parties. Ils avaient une structure de données primaire, dans laquelle les éléments sont stockés sans aucun bit gaspillé, et une structure de données secondaire, qui aide une requête de requête à trouver l'élément qu'elle recherche. Bien que le groupe n'ait pas inventé la notion de structure de données secondaire, ils ont fait une découverte cruciale qui a rendu possible leur table de hachage hyperefficace : l'efficacité globale de la mémoire de la structure dépend de la manière dont la structure primaire organise ses éléments stockés.

L'idée de base est que chaque élément de la structure principale a des emplacements de stockage préférés : un meilleur emplacement, un deuxième meilleur, un troisième meilleur, etc. Si un élément est à son meilleur endroit, le numéro 1 lui est apposé et ce numéro est stocké dans la structure de données secondaire. En réponse à une requête, la structure secondaire fournit uniquement le chiffre 1, qui indique l'emplacement exact de l'élément dans la structure primaire.

Si l'élément se trouve au 100e meilleur emplacement, la structure de données secondaire associe le nombre 100. Et comme le système utilise le binaire, il représente le nombre 100 comme 1100100. Il faut bien sûr plus de mémoire pour stocker le nombre 1100100 que 1. — le numéro attribué à un élément lorsqu'il se trouve au meilleur endroit. De telles différences deviennent significatives si vous stockez, disons, un million d'articles.

L'équipe a donc réalisé que si vous déplaciez continuellement les éléments de la structure de données principale vers leurs emplacements préférés, vous pourriez réduire considérablement la mémoire consommée par la structure secondaire sans avoir à augmenter les temps de requête.

"Avant ce travail, personne n'avait réalisé qu'il était possible de compresser davantage la structure des données en déplaçant les informations", a déclaré Pagh. "C'était la grande idée de l'article de Bender."

Les auteurs ont montré que leur invention établissait une nouvelle limite supérieure pour les tables de hachage les plus efficaces, ce qui signifie qu'il s'agissait de la meilleure structure de données jamais conçue en termes d'efficacité temporelle et spatiale. Mais il restait la possibilité que quelqu’un d’autre fasse encore mieux.

Vouloir réussir

L'année suivante, une équipe dirigée par Huacheng Yu, un informaticien de l'Université de Princeton, a tenté d'améliorer la table de hachage de l'équipe Bender. "Nous avons travaillé très dur et nous n'y sommes pas parvenus", a déclaré Renfei Zhou, étudiant à l'Université Tsinghua de Pékin et membre de l'équipe de Yu. « C'est à ce moment-là que nous avons soupçonné que leur limite supérieure était [également] une limite inférieure » – le meilleur qui puisse être atteint. "Lorsque la limite supérieure est égale à la limite inférieure, le jeu est terminé et vous avez votre réponse." Peu importe à quel point vous êtes intelligent, aucune table de hachage ne peut faire mieux.

L'équipe de Yu a utilisé une nouvelle stratégie pour découvrir si cette intuition était correcte en calculant une limite inférieure à partir des premiers principes. Premièrement, ils ont estimé que pour effectuer une insertion ou une suppression, une table de hachage – ou, en fait, n'importe quelle structure de données – devait accéder à la mémoire de l'ordinateur un certain nombre de fois. S'ils pouvaient déterminer le nombre minimum de fois nécessaire pour une table de hachage peu encombrante, ils pourraient le multiplier par le temps requis par accès (une constante), ce qui leur donnerait une limite inférieure sur le temps d'exécution.

Mais s’ils ne savaient rien de la table de hachage (sauf qu’elle était peu encombrante), comment les chercheurs pourraient-ils déterminer le nombre minimum de fois requis pour accéder à la mémoire ? Ils l’ont dérivé uniquement de la théorie, en utilisant un domaine apparemment sans rapport appelé la théorie de la complexité de la communication, qui étudie le nombre de bits nécessaires pour transmettre des informations entre deux parties. Finalement, l’équipe a réussi : elle a déterminé combien de fois une structure de données doit accéder à sa mémoire par opération.

C’était leur principale réussite. Ils ont ensuite pu établir une limite inférieure pour le temps d'exécution de toute table de hachage peu encombrante. Et ils ont vu que cela correspondait exactement à la table de hachage de Bender. "Nous avons pensé [au début] que cela pourrait être amélioré", a déclaré Zhou. "Il s'est avéré que nous avions tort." Cela signifiait que le problème de Peterson avait finalement été résolu.

En plus de répondre à une question vieille de plusieurs décennies, a déclaré Kuszmaul, ce qui est étonnant à propos de la preuve de Yu, c'est sa généralité. "Leur limite inférieure s'applique à toutes les structures de données possibles, y compris celles qui n'ont pas encore été inventées." Cela signifie qu'aucune méthode de stockage de données ne pourra jamais battre la table de hachage de Bender en termes de mémoire et de vitesse.

Hacher vers le futur

Malgré l’efficacité sans précédent de la nouvelle table de hachage, personne n’essaiera probablement de la construire de si tôt. C'est tout simplement trop compliqué à construire. "Un algorithme rapide en théorie ne l'est pas nécessairement en pratique", a déclaré Zhou.

Il n'est pas rare que de tels écarts entre la théorie et la pratique persistent longtemps, a expliqué Kuszmaul, car les théoriciens ont tendance à ignorer les facteurs constants. Le temps nécessaire pour effectuer une opération est généralement multiplié par un nombre, une constante dont la valeur exacte peut être sans importance d'un point de vue théorique. « Mais dans la pratique, les constantes comptent vraiment », a-t-il déclaré. "Dans le monde réel, un facteur 10 est la fin du jeu."

Les tables de hachage réelles continuent de s'améliorer de manière significative, même si elles sont loin de l'idéal théorique. Par exemple, une nouvelle table de hachage appelée IcebergHT, construit par Bender, Kuszmaul et d'autres, est bien meilleur que ses prédécesseurs. Selon Kuszmaul, elle est deux fois plus rapide que la table de hachage la plus économe en espace disponible aujourd'hui et utilise trois fois moins d'espace que la table de hachage la plus rapide.

Mitzenmacher espère que le résultat de 2023 pourrait bientôt apporter un autre type d’avantage : « Chaque fois que vous obtenez une nouvelle limite inférieure – en particulier celle qui implique de nouvelles techniques – il y a toujours l’espoir que vous puissiez les utiliser… pour des problèmes connexes. »

Il y a aussi la satisfaction intellectuelle qui vient de savoir que l'on a résolu un problème difficile et de longue date, a déclaré l'informaticien. Piotr Indyk du Massachusetts Institute of Technology. "Une fois que vous êtes sûr que certaines structures de données ne peuvent pas être améliorées, cela peut aider à concentrer les efforts de recherche." Enfin, les chercheurs en données peuvent détourner leur attention du défi de Peterson et se concentrer sur de nouveaux problèmes en informatique théorique, qui ne manquent pas.