Hash table : un accès rapide aux valeurs de hachage dans les bases de données
Où trouver le chapitre « Ce qui m’intéresse » dans un livre ? Où va la commande de Marie Dupont ? Où peut-on acheter cette montre avec un bracelet en cuir brun ? Quel est le point commun entre ces trois phrases ? Premièrement, il s’agit de trois questions. Ensuite, ces trois phrases portent sur un lieu (« Où ? »). Finalement, ces trois questions présupposent également que le résultat recherché existe. Ce modèle de pensée est facilement transposable aux bases de données.
Représentez-vous une boutique en ligne avec des milliers d’articles et de clients. Toutes ces données sont enregistrées dans des bases de données. Le client recherche un article précis dans la base de données et passe commande ; l’expéditeur associe l’article commandé à l’adresse du client via la base de données. Cette association entraîne diverses tâches de recherche et de tri ainsi que différents processus d’insertion et de suppression pendant le processus de commande. Pour faciliter la réalisation de ces tâches, les grands volumes de données appartenant à un même ensemble sont réunis sous une même position d’adressage dans la base de données. Cette position est calculée avec des valeurs de hachage et se compose ensuite d’un tableau avec des combinaisons de chiffres et de lettres de même longueur. Notre guide vous explique les principes d’utilisation de ces tables de hachage.
Quel est le principe d’une table de hachage ?
On calcule tout d’abord une valeur de hachage à partir des informations d’un ensemble de données. La table de hachage comprend les valeurs de hachage de tous les ensembles de données d’une base de données. Une seconde opération mathématique calcule la position d’enregistrement des informations dans la base de données à partir de la valeur de hachage. Lorsque l’utilisateur indique un mot-clé, celui-ci est également haché. On ne recherche alors plus la « montre avec un bracelet en cuir brun » mais une correspondance de la valeur hachée initialement pour l’article avec la valeur de hachage du mot-clé qui vient d’être utilisé, c’est-à-dire une correspondance entre deux séquences de chiffres et de lettres. Ce processus est utilisé pour des solutions très différentes.
Une plus grande sécurité grâce aux valeurs de hachage
On obtient une table de hachage en attribuant à des termes des valeurs de hachage générées automatiquement. La fonction de hachage utilisée à cet effet génère un « hash » (valeur de hachage), c’est-à-dire une suite de caractères disposant toujours de la même longueur. La longueur de la suite de caractère et les caractères qu’elle contient sont définis par la méthode de hachage utilisée. Ce procédé est par exemple utilisé pour accroître la sécurité des données d’accès contre les attaques.
Dans notre exemple de base de données WordPress, lors de la tentative de connexion, le mot de passe de l’utilisateur saisi est converti en valeur de hachage avec le même procédé, puis comparé avec l’entrée existant dans la base de données sous le champ « user_pass ». L’accès est autorisé si les deux valeurs de hachage de 34 caractères correspondent. Il est impossible de déchiffrer la valeur de hachage pour obtenir le mot de passe. C’est l’une des qualités des fonctions de hachage.
Dans le cas de tentatives d’intrusion – comme dans l’attaque par force brute –, il faudra alors tester cette chaîne de caractères avec tous les caractères autorisés pour parvenir à trouver une correspondance. En connaissant la fonction de hachage utilisée et en utilisant des majuscules, des minuscules et des chiffres dans un mot de passe de 10 caractères, il faudrait à un hacker précisément 839 299 365 868 340 200 tentatives pour déterminer une correspondance.
Un accès plus rapide aux bases de données
Dans les bases de données, les tables de hachage sont utilisées pour accélérer les procédures d’accès ainsi que la saisie et la suppression des ensembles de données. Par exemple, si l’on recherche un prénom dans une base de données répertoriant tous les employés d’une entreprise, cette recherche peut demander un temps considérable puisque les champs de la base de données sont analysés les uns après les autres (de façon séquentielle) afin de trouver une correspondance. En convertissant le mot-clé en valeur de hachage puis en recherchant une correspondance dans la table de hachage, on gagne généralement un temps considérable.
Comment ce processus se déroule-t-il ? Chaque ensemble de données reçoit une adresse unique. Ce type d’adressage est toujours identique au sein d’une base de données (001, 002, 003 ou 00A1, 00A2, 00A3, etc.). Cette adresse est calculée à l’aide d’une fonction de hachage.
Voici un exemple simple : prenons une base de données pouvant contenir 11 entrées, de la position 0 à 10. Le nom « Lisa » est composé de quatre caractères ASCII disposant de codes ASCII correspondants : L correspond à 76, i à 105, s à 115 et a à 97. Vous pouvez essayer par vous-même sous Windows : [Alt] + 0076 donne par exemple « L ». Si l’on additionne toutes les valeurs ASCII, cela nous donne la valeur de hachage 393 pour « Lisa ». L’addition des valeurs ASCII correspond ici à une fonction de hachage.
On procède alors au calcul de la valeur résiduelle avec des nombres entiers : 393 % 11 (positions) = 35, reste 8 (dans de nombreux langages de programmation, le symbole « % » est l’opérateur mathématique permettant de calculer la valeur résiduelle). Cette valeur résiduelle détermine à quelle position de la base de données – dans notre exemple, l’indice numéro 8 – seront enregistrées Lisa et toutes les autres données la concernant. On peut facilement imaginer qu’en utilisant ce type d’adressage, on obtient souvent la même valeur résiduelle. Toutefois, plus on a de positions d’enregistrement et plus la valeur de hachage est longue, moins il y aura de probabilité d’obtenir un tel doublon. Pour « Alis Meyer », on obtiendrait une tout autre position alors que le prénom comporte les « mêmes » lettres. Toutefois, comme le « A » est une majuscule et le « l » une minuscule, cela change la donne.
Le problème des doublons peut être observé dans notre schéma : il est tout à fait possible que des noms différents obtiennent le même indice provoquant ainsi des « collisions » (flèches bleu clair). Que « fait » la base de données de ces « collisions » ? Elle place l’ensemble de données à l’emplacement libre de la base de données le plus proche. Dans notre exemple, si l’on recherche « Berta Müller », la recherche ne commence pas à la position 001. Le pointeur de recherche est placé au début de la position d’indice 003, ce qui représente un (léger) gain de temps. Cette méthode, dans laquelle on effectue une recherche linéaire, est appelée hachage avec adressage ouvert.
L’adressage chaîné (chaînage) est une autre méthode dans laquelle aucun nouvel ensemble de données n’est « ouvert » et la seconde entrée pertinente est placée à la chaîne après la première entrée pertinente. De cette façon, il suffit d’une recherche pour trouver l’ensemble de données recherché situé à la même position d’enregistrement, « derrière » le premier ensemble de données. Cette méthode permet de gagner en rapidité de traitement.
Dès le début de la recherche de « Berta Müller », le pointeur de données est placé sur l’indice 003 calculé à partir de la table de hachage. Par conséquent, il est nécessaire d’explorer un seul ensemble de données chaîné. Cette méthode permet de rassembler de gros volumes de données de façon élégante et d’effectuer des recherches plus rapides.
Ce principe est également utilisé pour la mise en cache afin de pouvoir disposer plus rapidement des données déjà utilisées au préalable. Ces données sont enregistrées dans le cache – une mémoire temporaire – et peuvent y être consultées en cas de correspondance avec un modèle d’activité. Cela se produit notamment lorsque des utilisateurs ont déjà visité un site internet. Dans ce cas, le serveur ne doit pas charger à nouveau le site internet entièrement, puisque ce dernier peut être consulté directement depuis le cache qui offre un accès bien plus rapide. Une telle identification par comparaison est également réalisée par les cookies lorsque l’utilisateur a déjà visité un site internet.
Quelles variantes de hachage existe-t-il ?
La procédure de hachage qui vient d’être décrite est également appelée hachage ouvert ou externe. Dans ce cadre, les données peuvent être enregistrées dans des listes chaînées au sein d’un espace de stockage théoriquement illimité. Dans ce cas, on ne dispose plus de clés, mais le chaînage permet de gérer des volumes de données plus conséquents. L’adjectif « ouvert » renvoie à l’adressage ouvert.
Dans le hachage fermé, le nombre de clés disponibles est limité par la capacité de la table. Si l’on essaie d’enregistrer davantage de données, un débordement (overflow) se produit. Lorsque la table est à nouveau explorée, le système procède à un sondage pour savoir à quelles positions libres de tels « débordements » peuvent être placés.
L’utilisation des termes hachage « ouvert » et « fermé » n’est pas clairement établie. Dans les publications, ils sont parfois utilisés pour désigner le procédé opposé. Par conséquent, il est recommandé d’utiliser la description détaillée du procédé.
Le hachage du coucou sert également à éviter les collisions dans une table de base de données. Il doit son nom au comportement du coucou qui retire les œufs des nids des autres oiseaux pour y placer les siens. Deux fonctions de hachage sont donc utilisées pour définir deux positions d’enregistrement. Si la première position est déjà occupée, la clé qui s’y trouve est déplacée à une autre position alors que la seconde clé générée est placée à la première position d’enregistrement. L’inconvénient de cette méthode est qu’il peut se former une boucle de recherche infinie qui provoquera l’interruption d’une routine initiée du fait d’un dépassement de délai.
Pour sonder une base de données, il existe différentes méthodes élaborées à partir de formules mathématiques complexes. Sur les sites internet, elles sont dissimulées derrière un code de programme, par exemple derrière un simple champ de recherche représenté par une loupe.
En général, les bases de données sont régulièrement complétées et le volume de données augmente très rapidement. Le hachage dynamique tient compte de cette évolution en élargissant la table de hachage afin d’éviter les collisions. Cependant, cette extension implique que les valeurs de hachage des données déjà enregistrées changent au fur et à mesure que la table augmente. Des fonctions de hachage spéciales ont été développées pour apporter une solution à ce problème. De cette façon, il n’existe (en théorie) aucune limite au volume de données. Les processus de recherche sont toutefois moins efficaces.
Avantages et inconvénients des tables de hachage
Le principal avantage de l’utilisation d’une table de hachage est la possibilité d’effectuer une recherche rapide dans de très grands volumes de données. Cependant, les créateurs de la base de données doivent relever le défi d’estimer au préalable la taille nécessaire afin de limiter un maximum les risques de collisions. De nombreux types de données peuvent être utilisés pour autant que l’on puisse calculer des valeurs de hachage à partir de ces données.
Le point faible de cette approche réside notamment dans le fait que les bases de données peuvent se détériorer si une multitude de collisions se produit. La probabilité des collisions augmente en effet avec le volume de données. Par ailleurs, un grand nombre de fonctions de hachage ne permet pas de passer à l’ensemble de données suivant ou précédent.