Quelle est la structure des données Table de hachage (table de hachage) ? Quelles sont les opérations spécifiques ?

1. Qu'est-ce qu'une table de hachage

Si vous voulez savoir ce qu'est une table de hachage, vous devez d'abord comprendre la fonction de hachage

Hash fonction :

Par rapport à l'arbre de tri binaire évoqué dans le blog précédent, l'arbre binaire équilibré, l'arbre rouge-noir B et l'arbre B+, leur recherche commence à partir du nœud racine, puis supprime les données ou l'index et la valeur de recherche du nœud. Effectuez une comparaison. Alors, existe-t-il une fonction H ? Sur la base de cette fonction et de la clé du mot-clé de recherche, l'emplacement de la valeur de recherche peut être directement déterminé sans comparaison une par une. De cette façon, vous pouvez « connaître » l'emplacement de la clé à l'avance, retrouver les données directement et améliorer l'efficacité.

C'est-à-dire, index d'adresse = H (clé)

Pour parler franchement, la fonction de hachage calcule l'emplacement où l'adresse doit être stockée en fonction de la clé, et la table de hachage est un recherche basée sur la fonction de hachage

II, méthode de construction de la fonction de hachage

Selon l'expérience précédente, voici les méthodes de construction des fonctions de hachage couramment utilisées :

Méthode de personnalisation directe

La fonction de hachage est une fonction linéaire du mot-clé tel comme H (clé) = a* clé+b

Cette méthode de construction est relativement simple et uniforme, mais elle présente de grandes limites et se limite au cas où la taille de l'adresse = ensemble de mots-clés

Exemple d'utilisation :

Hypothèse Il est nécessaire de calculer la répartition par âge de la population chinoise, avec 10 comme plus petite unité. Cette année, nous sommes en 2018, donc les moins de 10 ans sont distribués en 2008-2018, et ceux de moins de 20 ans sont distribués en 1998-2008... En supposant que 2018 représente des données directes de 2018-2008, alors les mots-clés devraient être 2018. , 2008, 1998...

Ensuite la fonction de hachage H(key)=(2018-key)/10=201-key/10 peut être construite

Ensuite la table de hachage est établie comme suit

clé d'index âge nombre de personnes (données supposées)

0 2018 0-10 200W

1 2008 10-20 250W

2 1998 20-30 253W

3 1988 30- 40 300W

……

Méthode d'analyse numérique
Supposons que chaque mot-clé clé dans le mot-clé l'ensemble est composé de s chiffres (k1, k2,...,knk1,k2,...,kn), analyse toutes les données de la clé et extrait un certain nombre de bits uniformément répartis ou leur combinaison pour former le tout

Exemple d'utilisation

Nous sachant que les numéros d'identification sont réguliers, nous souhaitons maintenant stocker les numéros d'identification des élèves d'une classe. Supposons que les élèves de cette classe soient tous nés dans la même zone et. la même année, alors les premiers chiffres de leurs cartes d'identité sont les mêmes, alors nous pouvons intercepter les différents bits suivants à stocker. Supposons qu'il y ait 5 bits différents, puis utilisez ces cinq bits pour représenter l'adresse.

H(key)=key%100000

Cette méthode est généralement utilisée lorsque le nombre de chiffres est long. Il doit y avoir certaines règles dans les nombres et la distribution des nombres doit être. connus, comme celui ci-dessus. Par exemple, on sait à l'avance que les élèves de cette classe sont nés la même année et dans la même zone.

Méthode des carrés

S'il y a certains nombres qui apparaissent fréquemment dans chaque chiffre du mot-clé, vous pouvez d'abord trouver la valeur carrée du mot-clé, augmenter la différence par mise au carré, puis prenez le chiffre du milieu comme adresse de stockage finale.

Exemple d'utilisation

Par exemple, key=1234 1234^2=1522756, prenez 227 comme adresse de hachage

Par exemple, key=4321 4321^2=18671041, prenez 671 comme adresse de hachage

Cette méthode convient aux situations où les données ne sont pas connues à l'avance et où la longueur des données est petite

Méthode de pliage
Si le numéro a plusieurs chiffres, le numéro peut être divisé en plusieurs parties, prenez leur somme de superposition comme adresse de hachage
Exemple d'utilisation
Par exemple, key=123 456 789
On peut le stocker dans 61524, prenez les trois derniers chiffres, et il y a une position de 524
Cette méthode convient aux nombres Lorsqu'il y a beaucoup de chiffres et que la distribution des données n'est pas connue à l'avance

La méthode de division et de reste est souvent utilisée
H (clé) = clé MOD p (p Très évidemment, comment choisir p est une question clé.

Exemple d'utilisation

Par exemple, si nous stockons 3 6 9, alors p ne peut pas être 3

Parce que 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p doit être un nombre premier ne dépassant pas m ou un nombre composé sans facteur premier inférieur à 20, ce qui peut réduire la duplication d'adresses (conflits)

Par exemple, clé = 7, 39, 18, 24, 33. Lorsque 21, prenez la longueur du tableau m comme 9 et p comme 7, puis stockez-la comme suit :

Méthode des nombres aléatoires
H (key) = Random (key)
Prendre la valeur de fonction aléatoire du mot-clé comme adresse de hachage

Considérations sur la conception de la fonction de hachage

1. Le temps nécessaire pour calculer l'adresse de hachage (c'est-à-dire que la fonction de hachage elle-même ne devrait pas être trop compliquée)
2. longueur du mot-clé
3. Longueur du tableau
4. La distribution des mots-clés est-elle uniforme et régulière
5. La fonction de hachage est conçue pour minimiser les conflits si les conditions ci-dessus sont remplies

3. Conflit de hachage

C'est-à-dire que différentes valeurs de clé produisent la même adresse, H (clé1) = H (clé2)
Par exemple, lorsque nous stockons 3 6 9 ci-dessus, p prend 3 comme
3 MOD 3 == 6 MOD 3 == 9 MOD 3
À ce moment, des conflits de hachage se sont produits dans 3 6 9

La solution au hachage conflit

Peu importe l'intelligence avec laquelle la fonction de hachage est conçue, il y aura toujours des clés spéciales qui provoquent des conflits de hachage, en particulier pour les tables de recherche dynamiques.

La fonction de hachage dispose des méthodes courantes suivantes pour résoudre les conflits

1. Méthode de personnalisation ouverte

2. >

3. Méthode de zone de débordement publique

Créez un espace de stockage spécial spécifiquement pour stocker les données conflictuelles. Cette méthode convient aux situations où il y a moins de données et de conflits.

4. Méthode Rehash

Préparez plusieurs fonctions de hachage, utilisez la deuxième fonction de hachage. troisième...

Concentrez-vous sur la méthode de personnalisation ouverte et la méthode d'adresse en chaîne

La méthode de personnalisation ouverte

Il y a d'abord une fonction de hachage H (clé)

Si H(key1)=H(keyi)

Alors l'emplacement de stockage keyi Hi=(H(key)+di)MODmHi=(H(key)+di)MODmm est la longueur de la table

Notez que

incrément di doit avoir les caractéristiques suivantes (exhaustivité) : les Hi (adresses) générés ne sont pas les mêmes, et les s (m) générés -1) Hi peut couvrir toutes les adresses de la table de hachage

* Lors de la détection de carrés, la longueur de la table m doit être un nombre premier de 4j+3 (la longueur de la table de détection des carrés est limitée)

19 01 23 14 55 68 11 86 37 doit être stocké dans un tableau de longueur de table 11, où H (clé) = clé MOD 11

Suivez ensuite les trois méthodes de résolution de conflits ci-dessus pour store Le processus est le suivant : (Explication du tableau : Insérer les données de l'avant vers l'arrière. Si la position d'insertion est déjà occupée et qu'un conflit se produit, démarrez une nouvelle ligne pour le conflit et calculez l'adresse jusqu'à l'adresse est disponible. Continuez à démarrer une nouvelle ligne pour les conflits ultérieurs . Le résultat final est la donnée du haut (car ce sont les données les plus "occupantes"))

Détection linéaire puis hachage <.>

On prend di=1, c'est-à-dire Après le conflit, il est stocké dans la position après le conflit. S'il y a toujours un conflit, continuez en arrière

Détection de carrés puis hachage

Détection aléatoire après hachage (double détection puis hachage) Après collision

H(key)'=(H(key) +di)MOD m

Dans cet exemple H(key)=key MOD 11 Si on prend di=key MOD 10 +1 alors on a les résultats suivants :

Méthode d'adresse en chaîne

Après un conflit de hachage, ajoutez un pointeur après les données stockées pour pointer vers les données en conflit
Dans l'exemple ci-dessus, la méthode d'adresse en chaîne est comme suit :

4. Recherche dans la table de hachage

Le processus de recherche est le même que le processus de création de table. la méthode d'adressage ouverte est utilisée pour gérer les conflits, alors Le processus de recherche est :

Pour une clé donnée, calculer l'index de l'adresse de hachage = H (clé)

Si la valeur du tableau arr [index] est vide, la recherche échoue

Si le tableau arr[index] == clé, la recherche est réussie

Sinon, utilisez la méthode de résolution de conflit pour trouver l'adresse suivante jusqu'à arr[index] == key ou arr[index] == null

On peut voir que quelle que soit la fonction, plus le facteur de chargement est grand, plus la moyenne est grande longueur de recherche, alors plus le facteur de chargement α est petit, mieux c'est ? Non, tout comme une table d'une longueur de 100 ne stocke qu'une seule donnée, α est petit, mais l'utilisation de l'espace n'est pas élevée. Il s'agit d'un compromis entre le temps et l'espace. Dans des circonstances normales, α = 0,75 est considéré comme la situation où l’efficacité d’utilisation globale du temps et de l’espace est la plus élevée.

Le tableau ci-dessus est particulièrement utile. Supposons que j'ai maintenant 10 données, que je souhaite utiliser la méthode d'adresse en chaîne pour résoudre les conflits et que j'exige la longueur moyenne de recherche

, alors il y a 1+α/2

α

C'est-à-dire n/m

m>10/2

m>5 C'est-à-dire en utilisant l'adresse de la chaîne méthode, la longueur de recherche moyenne est 5

Mon blog a déjà discuté de la longueur de recherche moyenne de divers arbres. Ils sont tous basés sur des fonctions de stockage de données n, mais la table de hachage est différente. Il s'agit d'une fonction basée sur le facteur de chargement, c'est-à-dire que lorsque les données n augmentent, je peux augmenter la longueur de la table m pour maintenir le facteur de charge inchangé et garantir que l'ASL reste inchangé.

Ensuite, la structure de la table de hachage devrait être comme ceci :

5. Suppression de la table de hachage

Premièrement, la méthode d'adresse en chaîne peut supprimer directement des éléments, mais la méthode d'adressage ouverte ne peut pas prendre l'exemple de la double détection et du hachage précédents. Si nous supprimons l'élément 1 et laissons sa position vide, alors 23 ne sera jamais trouvé. La bonne approche devrait être d'insérer des données qui n'existent pas avant de les supprimer, telles que -1.

Pour plus de questions connexes, veuillez visiter le site Web PHP chinois : Tutoriel vidéo pratique PHP

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!