Gestion classique des conflits des tables de hachage (tables de hachage) dans les structures de données

Le hachage consiste à établir une certaine correspondance f entre l'emplacement de stockage de l'enregistrement et son mot-clé, de sorte que chaque clé de mot-clé corresponde à un emplacement de stockage f (clé), établissant la relation mutuelle entre le mot-clé et l'emplacement de stockage. relation, cette relation f est appelée fonction de hachage (fonction de hachage). L'éditeur de cet article parle principalement du problème de gestion des conflits de la fonction de hachage.

Pendant le processus de recherche, le nombre de comparaisons de codes clés dépend du nombre de conflits. Moins il y a de conflits, plus la recherche est élevée. l'efficacité, il y aura de nombreux conflits et l'efficacité de la recherche sera faible. Par conséquent, les facteurs qui affectent le nombre de conflits sont des facteurs qui affectent l'efficacité de la recherche. Il existe les trois facteurs suivants qui affectent le nombre de conflits :

1. Si la fonction de hachage est uniforme ;

2. La méthode de gestion des conflits ; Le facteur de remplissage de la table de hachage .

Le facteur de remplissage d'une table de hachage est défini comme : α = le nombre d'éléments remplis dans la table / la longueur de la table de hachage

α est un facteur signe du degré de remplissage de la table de hachage. Puisque la longueur du tableau est une valeur fixe, α est proportionnel au « nombre d'éléments remplis dans le tableau ». Par conséquent, plus α est grand, plus il y a d'éléments remplis dans le tableau, et plus le risque de conflit est grand ; α, moins il y a d’éléments dans le tableau, moins il y aura de risques de conflits.

En fait, la longueur moyenne de recherche d'une table de hachage est fonction du facteur de remplissage α, mais différentes méthodes de gestion des conflits ont des fonctions différentes.

Les méthodes pour résoudre les conflits de hachage incluent généralement :

Méthode d'adressage ouverte NO.1

La méthode d'adressage dite ouverte signifie qu'une fois qu'un conflit survient, recherchez le prochaine adresse vide. Tant que la table de hachage est suffisamment grande, l'adresse de hachage vide peut toujours être trouvée et l'enregistrement sera stocké.

Formule : f(key)=(f(key)+di)%m(di=1,2,3….m-1)

Par exemple, l'ensemble de mots-clés est {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}, la longueur du tableau est de 12. Fonction de hachage f(key) = clé mod 12.

Lors du calcul des cinq premiers nombres {12, 67, 56, 16, 25}, ce sont tous des adresses de hachage sans conflit et sont stockés directement lors du calcul de clé = 37, on constate que f(37) = 1. À l’heure actuelle, cela entre en conflit avec la position 25. Appliquez donc la formule ci-dessus f(37) = (f(37) + 1) mod 12 =2,. Donc 37 est stocké à l’emplacement d’index 2. Les 22, 29, 15 et 47 suivants n'ont aucun conflit et sont déposés normalement. En 48, on calcule f(48) = 0, ce qui entre en conflit avec la position 0 de 12. Ce n'est pas grave, on f(48) = (f(48) + 1) mod 12 = 1, ce qui maintenant entre en conflit avec la position de 25. conflit. Donc f(48) = (f(48) + 2) mod 12 = 2, il y a toujours un conflit... jusqu'à ce que f(48) = (f(48) + 6) mod 12 = 6, il y a des postes vacants indiqué dans le tableau ci-dessous.

16

Méthode de re-hachage NO.2

Pour les tables de hachage, plusieurs fonctions de hachage peuvent être préparées à l'avance.

Formule : fi(key)=RHi(key)(i=1,2,3...,k)

Ici RHi est une fonction de hachage différente, vous pouvez diviser et laisser le reste, le pliage, l'équarrissage et le centrage sont tous utilisés. Chaque fois qu'un conflit d'adresse de hachage se produit, une fonction de hachage différente est utilisée pour le calcul.

Cette méthode peut empêcher l'agrégation de mots clés, mais elle augmente également le temps de calcul en conséquence.

Méthode d'adresse en chaîne NO.3 (méthode zippé)

Stockez tous les enregistrements dont les mots-clés sont des synonymes dans une liste à chaînage unique. Ce type de liste est appelé sous-liste de synonymes. Seuls les pointeurs vers le début de toutes les sous-listes de synonymes sont stockés dans la table de hachage. Pour l'ensemble de mots-clés {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}, utilisez le même 12 que le reste comme avant et exécutez la méthode de division et de reste pour obtenir la structure ci-dessous.

NO.4 Créer une zone de débordement publique

Cette méthode consiste à trouver une nouvelle adresse pour vous et à créer une zone de débordement publique pour tous les mots-clés en conflit. zone de débordement pour le stockage.

En ce qui concerne l'exemple précédent, il y a trois mots-clés 37, 48 et 34 qui entrent en conflit avec les positions de mots-clés précédentes, stockez-les donc dans la table de débordement. Comme indiqué ci-dessous.

Lors de la recherche, après avoir calculé l'adresse de hachage de la valeur donnée via la fonction de hachage, elle est d'abord comparée à la position correspondante dans le tableau de base si elles sont égales, recherche Succès ; s'il n'est pas égal, effectuez une recherche séquentielle dans la table de débordement. S'il y a très peu de données contradictoires par rapport au tableau de base, la structure de la zone de débordement commune reste très élevée pour les performances de recherche.

[Cours recommandés : Cours liés au C++]

Numéro de série

0

1

2

3

4

5

6

7

8

9

10

11

Mots clés

12

25

序号	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25			16			67	56

67

56

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!