Différence entre le hachage dynamique et statique

Dans la structure des données, le hachage est une technique de cartographie du grand nombre d'éléments de données à des tables plus petites en utilisant une fonction spéciale appelée fonction de hachage pour un accès plus rapide. Parfois, la structure des données est si énorme qu'elle devient presque presque 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 le hachage arrive juste. Ce qu'il fait, c'est qu'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 disponibles en utilisant les fonctions de hachage - hachage dynamique et hachage statique.

Qu'est-ce que le hachage statique?

Le hachage statique est une méthode de hachage dans laquelle un nombre fixe de seaux est alloué à un fichier pour stocker les enregistrements. Le nombre de seaux est pré-alloué, donc 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 seaux, 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 d'une manière que le nombre d'entrées d'index dans chaque seau est à peu près la même. Cependant, il y a aussi certains inconvénients à ce schéma. Si le nombre initial de seaux est trop petit et que le fichier augmente, les performances se dégradent en raison des débordements du seau. D'un autre côté, s'il est trop grand, beaucoup d'espace est alloué à la croissance anticipée et une quantité importante d'espace se gaspille.

Qu'est-ce que le hachage dynamique?

Le hachage dynamique, en revanche, est une technique utilisée pour surmonter les limites du hachage statique comme un débordement de seau. Contrairement à un hachage statique, il permet au nombre de seaux de varier dynamiquement pour s'adapter à la croissance ou au retrait des fichiers de base de données. Il permet à la fonction de hachage d'être modifiée à la demande, ce qui est bon pour les bases de données qui se développent et rétrécissent en taille. Au fur et à mesure que les lignes sont ajoutées et supprimées, il modifie le nombre de seaux en conséquence afin de minimiser le débordement de seaux. Il incorpore la manipulation des enregistrements de débordement dans son espace d'adresse primaire dynamiquement afin d'éviter la gestion de la gestion des seaux 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 du seau en divisant un seau en deux, distribuant les enregistrements entre les anciens et les nouveaux seaux. Le hachage linéaire est encore une autre forme populaire de hachage dynamique qui permet à un fichier de hachage de se développer ou de rétrécir dynamiquement en allouant de nouveaux seaux.

Différence entre le hachage dynamique et statique

Technique

- Le hachage statique est une méthode de hachage dans laquelle un nombre fixe de seaux 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 godet est fixé. Ici, les entrées d'index sont randomisées d'une manière que le nombre d'entrées d'index dans chaque seau est à peu près la même. Le hachage dynamique, en revanche, permet au nombre de seaux de varier dynamiquement afin de s'adapter à la croissance ou au retrait des fichiers de base de données.

Performance

- Si le nombre initial de seaux est trop petit et que le fichier augmente, les performances se dégradent en raison des débordements du seau. D'un autre côté, s'il est trop grand, beaucoup d'espace est alloué à la croissance anticipée et une quantité importante d'espace se gaspille. Le hachage dynamique, en revanche, permet à la fonction de hachage d'être modifiée dynamiquement, ce qui est bon pour les bases de données qui se développent et se rétrécissent en taille. Au fur et à mesure que les lignes sont ajoutées et supprimées, il modifie le nombre de seaux en conséquence afin de minimiser le débordement de seaux.

Mise en œuvre

- Static Hashing utilise une fonction de hachage fixe pour partitionner l'ensemble de toutes les valeurs possibles de la clé de recherche en sous-ensembles, puis cartocie chaque sous-ensemble à un seau. Le hachage dynamique, en revanche, utilise une deuxième étape de cartographie pour déterminer le seau associé à une valeur de clé de recherche. Extensible et hachage linéaire fait cette cartographie très différemment.

Dynamique vs. Hachage statique: tableau de comparaison

Résumé

Le nombre de seaux est fixé dans le hachage statique et les enregistrements avec différentes valeurs de clé de recherche pointent vers le même seau, auquel cas une collision peut se produire. Si vous devez localiser un enregistrement spécifique dans un seau avec plusieurs clés, vous devez rechercher l'ensemble du seau séquentiellement. Parfois, un seau a plus d'enregistrements qu'il ne peut contenir. Ainsi, dans ce cas, certaines techniques de manutention de débordement doivent être invoquées. Dans ce cas, un hachage dynamique est utilisé, qui utilise une fonction changeante dynamiquement qui permet au nombre de seaux alloués de croître et de rétrécir à mesure que les lignes sont ajoutées et supprimées. Il gère explicitement le débordement de seaux en intégrant les enregistrements de débordement dynamiquement dans son adresse principale.