Dans le domaine de la structure des données, le hachage est une technique qui consiste à faire correspondre un grand nombre d’éléments de données à des tables plus petites à l’aide d’une fonction spéciale appelée fonction de hachage, afin d’accélérer l’accès. Parfois, la structure de données est tellement vaste qu’il est pratiquement impossible de rechercher toutes les valeurs d’index à travers tous les niveaux afin d’accéder au bloc de données final. C’est là que la fonction de hachage entre en jeu. Il calcule l’emplacement d’un enregistrement de données sur le disque directement sans utiliser la structure d’index. L’adresse de chaque enregistrement est déterminée à l’aide d’un algorithme de hachage, qui convertit une valeur de clé primaire en une adresse d’enregistrement. Il existe donc deux catégories d’indexation utilisant des fonctions de hachage : le hachage dynamique et le hachage statique.
Qu’est-ce que le hachage statique ?
Le hachage statique est une méthode de hachage dans laquelle un nombre fixe de godets est alloué à un fichier pour stocker les enregistrements. Le nombre de godets est pré-alloué de sorte que lorsqu’une valeur de clé de recherche est fournie, la fonction de hachage calcule toujours la même adresse. La page d’un fichier peut être considérée comme une collection de godets, avec une page principale et des pages de débordement supplémentaires. Avec le hachage statique, le mécanisme de localisation est la fonction de hachage et aucune structure de données n’est impliquée. Ici, les entrées d’index sont randomisées de manière à ce que le nombre d’entrées d’index dans chaque godet soit à peu près le même. Toutefois, ce système présente également certains inconvénients. Si le nombre initial de godets est trop faible et que le fichier augmente, les performances se dégradent en raison du débordement des godets. D’autre part, si le nombre de godets est trop élevé, beaucoup d’espace est alloué à la croissance anticipée et une grande partie de l’espace est perdue.
Qu’est-ce que le Dynamic Hashing ?
Le hachage dynamique, quant à lui, est une technique utilisée pour surmonter les limites du hachage statique, comme le débordement des godets. Contrairement au hachage statique, il permet de faire varier le nombre de godets de manière dynamique afin de s’adapter à la croissance ou à la réduction des fichiers de la base de données. La fonction de hachage peut être modifiée à la demande, ce qui est utile pour les bases de données dont la taille augmente ou diminue. Lorsque des lignes sont ajoutées ou supprimées, le nombre de godets est modifié en conséquence afin de minimiser le débordement des godets. Il intègre dynamiquement la gestion des enregistrements de débordement dans son espace d’adressage primaire afin d’éviter la gestion des buckets de débordement. Les deux formes de hachage dynamique couramment utilisées sont le hachage linéaire et le hachage extensible. Le hachage extensible est une technique populaire qui gère le débordement des godets en divisant un godet en deux, répartissant les enregistrements entre l’ancien et le nouveau godet. Le hachage linéaire est une autre forme populaire de hachage dynamique qui permet à un fichier de hachage de croître ou de diminuer dynamiquement en allouant de nouveaux godets.
Différence entre le hachage dynamique et le hachage statique
La technique
– Le hachage statique est une méthode de hachage dans laquelle un nombre fixe de godets est alloué à un fichier pour stocker les enregistrements, ce qui signifie qu’il utilise une fonction de hachage dans laquelle le nombre d’adresses de godets est fixe. Dans ce cas, les entrées d’index sont randomisées de manière à ce que le nombre d’entrées d’index dans chaque godet soit à peu près le même. Le hachage dynamique, quant à lui, permet de faire varier le nombre de godets de manière dynamique afin de s’adapter à la croissance ou à la réduction des fichiers de la base de données.
Performance
– Si le nombre initial de godets est trop faible et que le fichier augmente, les performances se dégradent en raison du débordement des godets. En revanche, s’il est trop grand, une grande partie de l’espace est allouée à la croissance anticipée et une grande partie de l’espace est perdue. Le hachage dynamique, quant à lui, permet de modifier la fonction de hachage de manière dynamique, ce qui est intéressant pour les bases de données dont la taille augmente et diminue. Au fur et à mesure que des lignes sont ajoutées et supprimées, le nombre de godets est modifié en conséquence afin de minimiser le débordement des godets.
Mise en œuvre
– Le hachage statique utilise une fonction de hachage fixe pour diviser l’ensemble de toutes les valeurs possibles de la clé de recherche en sous-ensembles, puis fait correspondre chaque sous-ensemble à un panier. Le hachage dynamique, quant à lui, utilise une deuxième étape de mise en correspondance pour déterminer le panier associé à une certaine valeur de clé de recherche. Le hachage extensible et le hachage linéaire effectuent cette mise en correspondance de manière très différente.
Résumé
Le nombre de godets est fixe dans le hachage statique et les enregistrements ayant des valeurs de clé de recherche différentes pointent vers le même godet, auquel cas une collision peut se produire. Si vous devez localiser un enregistrement spécifique dans un panier avec plusieurs clés, vous devez effectuer une recherche séquentielle dans l’ensemble du panier. Il arrive qu’un seau contienne plus d’enregistrements qu’il ne peut en contenir. Dans ce cas, des techniques de gestion des débordements doivent être utilisées. Dans ce cas, on utilise le hachage dynamique, qui fait appel à une fonction changeant dynamiquement qui permet au nombre de godets alloués d’augmenter et de diminuer en taille au fur et à mesure que des lignes sont ajoutées et supprimées. Il gère explicitement le débordement des godets en intégrant dynamiquement les enregistrements de débordement dans son adresse primaire.