Qu’est-ce que la table de hachage ?

Une table de hachage est définie comme une structure de données utilisée pour insérer, rechercher et supprimer rapidement des paires clé-valeur. Il opère sur le notion de hachage , où chaque clé est traduite par une fonction de hachage en un index distinct dans un tableau. L'index fonctionne comme un emplacement de stockage pour la valeur correspondante. En termes simples, il mappe les clés avec la valeur.

Qu'est-ce que le facteur de charge ?

Le facteur de charge d’une table de hachage est déterminé par le nombre d’éléments qui y sont conservés par rapport à la taille de la table. La table peut être encombrée et avoir des temps de recherche et des collisions plus longs si le facteur de charge est élevé. Un facteur de charge idéal peut être maintenu grâce à l’utilisation d’une bonne fonction de hachage et d’un redimensionnement approprié de la table.

Qu'est-ce qu'une fonction de hachage ?

Une fonction qui traduit les clés en indices de tableau est connue sous le nom de fonction de hachage. Les clés doivent être réparties uniformément sur le tableau via une fonction de hachage décente pour réduire les collisions et garantir des vitesses de recherche rapides.

• Hypothèse d'univers entier : Les clés sont supposées être des nombres entiers dans une certaine plage selon l'hypothèse de l'univers entier. Cela permet d'utiliser des opérations de hachage de base telles que le hachage de division ou de multiplication.
• Hachage par division : Cette technique de hachage simple utilise la valeur restante de la clé après l’avoir divisée par la taille du tableau comme index. Lorsque la taille d'un tableau est un nombre premier et que les clés sont régulièrement espacées, cela fonctionne bien.
• Hachage par multiplication : Cette opération de hachage simple multiplie la clé par une constante comprise entre 0 et 1 avant de prendre la partie fractionnaire du résultat. Après cela, l’indice est déterminé en multipliant la composante fractionnaire par la taille du tableau. En outre, il fonctionne efficacement lorsque les touches sont réparties de manière égale.

Choisir une fonction de hachage :

La sélection d'une fonction de hachage décente est basée sur les propriétés des clés et la fonctionnalité prévue de la table de hachage. L’utilisation d’une fonction qui répartit uniformément les clés et réduit les collisions est cruciale.

Critères sur la base desquels une fonction de hachage est choisie :

• Pour garantir que le nombre de collisions soit réduit au minimum, une bonne fonction de hachage doit répartir les clés de manière uniforme dans la table de hachage. Cela implique que pour toutes les paires de clés, la probabilité que deux clés soient hachées vers la même position dans le tableau devrait être plutôt constante.
• Pour permettre un hachage et une récupération rapides des clés, la fonction de hachage doit être efficace sur le plan informatique.
• Il devrait être difficile de déduire la clé de sa valeur de hachage. Par conséquent, les tentatives visant à deviner la clé à l’aide de la valeur de hachage ont moins de chances de réussir.
• Une fonction de hachage doit être suffisamment flexible pour s'ajuster à mesure que les données hachées changent. Par exemple, la fonction de hachage doit continuer à fonctionner correctement si les clés hachées changent de taille ou de format.

Techniques de résolution des collisions :

Des collisions se produisent lorsque deux clés ou plus pointent vers le même index de tableau. Le chaînage, l'adressage ouvert et le double hachage sont quelques techniques permettant de résoudre les collisions.

• Adressage ouvert : les collisions sont gérées en recherchant l'espace vide suivant dans le tableau. Si le premier emplacement est déjà occupé, la fonction de hachage est appliquée aux emplacements suivants jusqu'à ce qu'il en reste un vide. Il existe différentes manières d'utiliser cette approche, notamment le double hachage, le sondage linéaire et le sondage quadratique.
• Chaînage séparé : Dans un chaînage séparé, une liste chaînée d'objets hachés vers chaque emplacement de la table de hachage est présente. Deux clés sont incluses dans la liste chaînée si elles sont hachées vers le même emplacement. Cette méthode est plutôt simple à utiliser et permet de gérer plusieurs collisions.
• Hachage de Robin des Bois : Pour réduire la longueur de la chaîne, les collisions dans le hachage Robin Hood sont résolues en désactivant les clés. L'algorithme compare la distance entre l'emplacement et l'emplacement occupé des deux clés si une nouvelle clé est hachée vers un emplacement déjà occupé. La clé existante est remplacée par la nouvelle si elle est plus proche de son emplacement idéal. Cela rapproche la clé existante de son emplacement idéal. Cette méthode a tendance à réduire les collisions et la longueur moyenne de la chaîne.

Redimensionnement dynamique :

Cette fonctionnalité permet à la table de hachage de s'étendre ou de se contracter en réponse aux modifications du nombre d'éléments contenus dans la table. Cela favorise un facteur de charge idéal et des temps de recherche rapides.

Implémentations de la table de hachage

Python, Java, C++ et Ruby ne sont que quelques-uns des langages de programmation prenant en charge les tables de hachage. Ils peuvent être utilisés comme structure de données personnalisée en plus d'être fréquemment inclus dans la bibliothèque standard.

Exemple – Comptez les caractères dans les String geeksforgeeks.

Dans cet exemple, nous utilisons une technique de hachage pour stocker le nombre de chaînes.

première recherche en profondeur de l'algorithme

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Sortir:

The count of e is 4>

Analyse de complexité d'une table de hachage :

Pour les opérations de recherche, d'insertion et de suppression, les tables de hachage ont une complexité temporelle moyenne de O(1). Pourtant, ces opérations peuvent, dans le pire des cas, nécessiter un temps O(n), où n est le nombre d'éléments dans le tableau.

Applications de la table de hachage :

• Les tables de hachage sont fréquemment utilisées pour indexer et rechercher d’énormes volumes de données. Un moteur de recherche peut utiliser une table de hachage pour stocker les pages Web qu'il a indexées.
• Les données sont généralement mises en cache en mémoire via des tables de hachage, permettant un accès rapide aux informations fréquemment utilisées.
• Les fonctions de hachage sont fréquemment utilisées en cryptographie pour créer des signatures numériques, valider des données et garantir leur intégrité.
• Les tables de hachage peuvent être utilisées pour implémenter des index de bases de données, permettant un accès rapide aux données basées sur des valeurs clés.