Introduction à la fonction de hachage en C
Cet article contient une brève note sur le hachage (table de hachage et fonction de hachage). Le concept le plus important est la «recherche» qui détermine la complexité temporelle. Pour réduire la complexité temporelle, tout autre concept de hachage de structure de données est introduit, qui a un temps O (1) dans le cas moyen et le pire des cas, cela prendra du temps O (n).
Le hachage est une technique avec un accès plus rapide aux éléments qui mappe les données données avec une clé moindre pour les comparaisons. En général, dans cette technique, les clés sont tracées à l'aide de la fonction de hachage dans une table connue sous le nom de table de hachage.
Qu'est-ce que la fonction de hachage?
La fonction de hachage est une fonction qui utilise l'opération à temps constant pour stocker et récupérer la valeur de la table de hachage, qui est appliquée sur les clés sous forme d'entiers et qui est utilisée comme adresse pour les valeurs de la table de hachage.
Types d'une fonction de hachage
Les types de fonctions de hachage sont expliqués ci-dessous:
1. Méthode de division
Dans cette méthode, la fonction de hachage dépend du reste d'une division.
Exemple: les éléments à placer dans une table de hachage sont 42, 78, 89, 64 et prenons la taille de la table comme 10.
Hash (clé) = Elements% size table;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
La représentation du tableau peut être vue comme ci-dessous:
2. Méthode du carré moyen
Dans cette méthode, la partie médiane de l'élément carré est prise comme indice.
Les éléments à placer dans la table de hachage sont 210, 350, 99, 890 et la taille de la table est 100.
210 * 210 = 44100, index = 1 car la partie médiane du résultat (44100) est 1.
350 * 350 = 122500, index = 25 car la partie médiane du résultat (122500) est 25.
99 * 99 = 9801, indice = 80 car la partie médiane du résultat (9801) est 80.
890 * 890 = 792100, index = 21 car la partie centrale du résultat (792100) est 21.
3. Méthode de pliage des chiffres
Dans cette méthode, l'élément à placer dans la table uh est la clé de hachage sing, qui est obtenue en divisant les éléments en différentes parties, puis en combinant les parties en effectuant quelques opérations mathématiques simples.
Les éléments à placer sont 23576623, 34687734.
- hachage (clé) = 235 + 766 + 23 = 1024
- clé de hachage) = 34 + 68 + 77 + 34 = 213
Dans ces types de hachage, supposons que nous ayons des nombres de 1 à 100 et que la taille de la table de hachage = 10. Éléments = 23, 12, 32
Hachage (clé) = 23% 10 = 3;
Hachage (clé) = 12% 10 = 2;
Hachage (clé) = 32% 10 = 2;
De l'exemple ci-dessus, notez que les deux éléments 12 et 32 pointent à la 2e place du tableau, où il n'est pas possible d'écrire les deux au même endroit, un tel problème est appelé collision. Pour éviter ce type de problèmes, certaines techniques de fonctions de hachage peuvent être utilisées.
Types de techniques de résolution des collisions
Laissez-nous discuter des types de techniques de résolution de collision:
1. Chaînage
Dans cette méthode, comme son nom l'indique, elle fournit une chaîne de cases pour l'enregistrement dans le tableau ayant deux entrées d'éléments. Ainsi, chaque fois que de telles collisions se produisent, les boîtes agissent comme une liste chaînée sera formée.
Exemple: 23, 12, 32 avec une taille de table 10.
Hachage (clé) = 23% 10 = 3;
Hachage (clé) = 12% 10 = 2;
Hachage (clé) = 32% 10 = 2;
2. Adressage ouvert
- Sondage linéaire
Il s'agit d'une autre méthode pour résoudre les problèmes de collision. Comme son nom l'indique chaque fois qu'une collision se produit, deux éléments doivent être placés sur la même entrée dans le tableau, mais par cette méthode, nous pouvons rechercher le prochain espace vide ou l'entrée dans le tableau et placer le deuxième élément. Cela peut à nouveau conduire à un autre problème; si nous ne trouvons aucune entrée vide dans le tableau, cela conduit au clustering. Ainsi, cela est connu comme un problème de clustering, qui peut être résolu par la méthode suivante.
Exemple: 23, 12, 32 avec taille de table 10
Hachage (clé) = 23% 10 = 3;
Hachage (clé) = 12% 10 = 2;
Hachage (clé) = 32% 10 = 2;
Dans ce diagramme 12 et 32 peuvent être placés dans la même entrée avec l'index 2 mais par cette méthode, ils sont placés linéairement.
- Sondage quadratique
Cette méthode est une résolution du problème de clustering pendant le sondage linéaire. Dans cette méthode, la fonction de hachage avec clé de hachage est calculée comme suit: hachage (clé) = (hachage (clé) + x * x)% de la taille de la table (où x = 0, 1, 2…).
Exemple: 23, 12, 32 avec taille de table 10
Hachage (clé) = 23% 10 = 3;
Hachage (clé) = 12% 10 = 2;
Hachage (clé) = 32% 10 = 2;
En cela, nous pouvons voir que 23 et 12 peuvent être placés facilement, mais 32 ne peuvent pas comme 12 et 32 partagent la même entrée avec le même index dans le tableau, selon cette méthode hash (clé) = (32 + 1 * 1) % 10 = 3. Mais dans ce cas, l'entrée de table avec l'index 3 est placée avec 23, nous devons donc incrémenter la valeur x de 1. Hash (clé) = (32 + 2 * 2)% 10 = 6. Nous pouvons donc maintenant placer 32 dans l'entrée avec l'index 6 dans le tableau.
- Double hachage
Cette méthode, nous devons calculer 2 fonctions de hachage pour résoudre le problème de collision. Le premier est calculé à l'aide d'une méthode de division simple. La seconde doit satisfaire deux règles; il ne doit pas être égal à 0 et les entrées doivent être sondées.
- 1 (clé) = clé% taille de la table.
- 2 (clé) = p - (mod clé p), où p est un nombre premier <taille de la table.
Exemple: 23, 12, 32 avec taille de table 10
Hachage (clé) = 23% 10 = 3;
Hachage (clé) = 12% 10 = 2;
Hachage (clé) = 32% 10 = 2;
Dans cela encore, l'élément 32 peut être placé en utilisant hash2 (clé) = 5 - (32% 5) = 3. Ainsi, 32 peut être placé à l'index 5 dans le tableau qui est vide car nous devons sauter 3 entrées pour le placer.
Fonction de conclusion-hachage en C
Le hachage est l'une des techniques importantes en termes de recherche de données fournies avec des méthodes très efficaces et rapides utilisant la fonction de hachage et les tables de hachage. Chaque élément peut être recherché et placé à l'aide de différentes méthodes de hachage. Cette technique est très plus rapide que toute autre structure de données en termes de coefficient de temps.
Articles recommandés
Ceci est un guide de la fonction de hachage en C. Ici, nous discutons de l'introduction de la fonction de hachage en C, Qu'est-ce que la fonction de hachage, Types de fonction de hachage, etc. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus–
- Hachage dans un SGBD
- Processus de cryptage
- Comment installer CakePHP?
- Comment fonctionne la blockchain
- Fonction de hachage en Java
- Fonction de hachage en PHP | Comment travailler?