Nouveaux travaux sur les tables de hachage à sondage linéaire de AVEC CSAIL pourrait conduire à un stockage et une récupération des données plus efficaces dans les ordinateurs.
Un trio de chercheurs qui comprend William Kuszmaul – un doctorant en informatique au MIT – a fait une découverte qui pourrait conduire à un stockage et une récupération de données plus efficaces dans les ordinateurs.
Les découvertes de l’équipe concernent les soi-disant « tables de hachage à sondage linéaire », qui ont été introduites en 1954 et sont parmi les structures de données les plus anciennes, les plus simples et les plus rapides disponibles aujourd’hui. Les structures de données fournissent des moyens d’organiser et de stocker des données dans des ordinateurs, les tables de hachage étant l’une des approches les plus couramment utilisées. Dans une table de hachage à sondage linéaire, les positions dans lesquelles les informations peuvent être stockées se trouvent le long d’un réseau linéaire.
Supposons, par exemple, qu’une base de données soit conçue pour stocker les numéros de sécurité sociale de 10 000 personnes, suggère Kuszmaul. « Nous prenons votre numéro de sécurité sociale, x, et nous calculerons ensuite la fonction de hachage de x, h(x), qui vous donne un nombre aléatoire compris entre un et 10 000 ». L’étape suivante consiste à prendre ce nombre aléatoire, h(x), à aller à cette position dans le tableau et à mettre x, le numéro de sécurité sociale, à cet endroit.
S’il y a déjà quelque chose qui occupe cette place, dit Kuszmaul, « vous avancez simplement vers la prochaine position libre et mettez-la là. C’est de là que vient le terme « sondage linéaire », alors que vous continuez à avancer linéairement jusqu’à ce que vous trouviez un espace libre. » Afin de récupérer plus tard ce numéro de sécurité sociale, x, vous allez simplement à l’endroit désigné, h(x), et s’il n’y est pas, vous avancez jusqu’à ce que vous trouviez x ou arriviez à une position libre et concluez que x est pas dans votre base de données.
Il existe un protocole quelque peu différent pour supprimer un élément, tel qu’un numéro de sécurité sociale. Si vous venez de laisser un espace vide dans la table de hachage après avoir supprimé les informations, cela pourrait causer de la confusion lorsque vous essaierez plus tard de trouver autre chose, car l’emplacement vacant pourrait suggérer à tort que l’élément que vous recherchez est introuvable dans la base de données. Pour éviter ce problème, explique Kuszmaul, “vous pouvez vous rendre à l’endroit où l’élément a été supprimé et y mettre un petit marqueur appelé” pierre tombale “, qui indique qu’il y avait un élément ici, mais qu’il a disparu maintenant. “
Cette procédure générale est suivie depuis plus d’un demi-siècle. Mais pendant tout ce temps, presque tout le monde utilisant des tables de hachage à sondage linéaire a supposé que si vous leur permettez d’être trop pleins, de longues étendues de points occupés se regrouperaient pour former des « clusters ». En conséquence, le temps qu’il faut pour trouver une place libre augmenterait considérablement – de manière quadratique, en fait – prenant tellement de temps qu’il serait impraticable. Par conséquent, les gens ont été formés pour utiliser des tables de hachage à faible capacité – une pratique qui peut coûter cher en affectant la quantité de matériel qu’une entreprise doit acheter et entretenir.
Mais ce principe séculaire, qui a longtemps milité contre des facteurs de charge élevés, a été totalement bouleversé par les travaux de Kuszmaul et de ses collègues, Michael Bender de l’université Stony Brook et Bradley Kuszmaul de Google. Ils ont découvert que pour les applications où le nombre d’insertions et de suppressions reste à peu près le même – et la quantité de données ajoutées est à peu près égale à celle supprimée – les tables de hachage à sondage linéaire peuvent fonctionner à des capacités de stockage élevées sans sacrifier la vitesse.
En outre, l’équipe a mis au point une nouvelle stratégie, appelée « hachage de cimetière », qui consiste à augmenter artificiellement le nombre de pierres tombales placées dans un tableau jusqu’à ce qu’elles occupent environ la moitié des emplacements libres. Ces pierres tombales réservent alors des espaces qui peuvent être utilisés pour de futures insertions.
Cette approche, qui va à l’encontre de ce que les gens ont l’habitude de faire, dit Kuszmaul, “peut conduire à des performances optimales dans les tables de hachage à sondage linéaire”. Ou, comme lui et ses coauteurs le maintiennent dans leur article, « l’utilisation bien conçue des pierres tombales peut complètement changer le… paysage du comportement du sondage linéaire ».
Kuszmaul a rédigé ces découvertes avec Bender et Kuszmaul dans un article publié plus tôt cette année qui sera présenté en février au Symposium Foundations of Computer Science (FOCS) à Boulder, Colorado.
Le directeur de thèse de doctorat de Kuszmaul, le professeur d’informatique du MIT Charles E. Leiserson (qui n’a pas participé à cette recherche), est d’accord avec cette évaluation. “Ces résultats nouveaux et surprenants renversent l’une des plus anciennes idées reçues sur le comportement des tables de hachage”, déclare Leiserson. “Les leçons se répercuteront pendant des années parmi les théoriciens et les praticiens.”
Quant à la traduction de leurs résultats dans la pratique, note Kuszmaul, « il y a de nombreuses considérations qui entrent en ligne de compte dans la construction d’une table de hachage. Bien que nous ayons considérablement avancé l’histoire d’un point de vue théorique, nous commençons tout juste à explorer le côté expérimental des choses.
Référence : « Linear Probing Revisited : Tombstones Mark the Death of Primary Clustering » par Michael A. Bender, Bradley C. Kuszmaul et William Kuszmaul, 2 juillet 2021, Informatique > Structures de données et algorithmes.
arXiv : 2107.01250
