Le hachage est une technique populaire utilisée pour stocker et récupérer des données le plus rapidement possible. La principale raison de l'utilisation du hachage est qu'il effectue des opérations d'insertion, de suppression, de recherche et autres.

Pourquoi utiliser le hachage ?

Lors du hachage, toutes les opérations telles que l'insertion, la recherche et la suppression peuvent être effectuées en O(1), c'est-à-dire en temps constant. La complexité temporelle du pire cas pour le hachage reste O(n), mais la complexité temporelle moyenne est O(1).

Table de hachage

Utilisé pour créer une nouvelle table de hachage.

Syntaxe:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Opérations de base avec syntaxe

Obtenir:

Utilisé pour rechercher une clé dans la table de hachage et renvoyer la valeur associée à cette clé.

Syntaxe:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

Insérer:

Utilisé pour insérer une nouvelle paire clé-valeur dans la table de hachage.

Syntaxe:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

Recherche:

Utilisé pour rechercher une valeur.

Syntaxe:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

Supprimer:

Utilisé pour supprimer une paire clé-valeur particulière de la table de hachage.

Syntaxe:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Composants du hachage en Javascript

1. Table de hachage : Une table de hachage est une généralisation du tableau. Il offre la fonctionnalité dans laquelle une collection de données est stockée de telle manière qu'il est facile de retrouver ces éléments ultérieurement si nécessaire. Cela rend la recherche d'un élément très efficace.

2. Fonction de hachage : Une fonction de hachage est utilisée pour transformer une clé donnée en un index d'emplacement spécifique. il est utilisé pour mapper chaque clé possible dans un index d'emplacement unique. Si chaque clé est mappée dans un index d'emplacement unique, alors la fonction de hachage est connue sous le nom de fonction de hachage parfaite. Il est très difficile de créer une fonction de hachage parfaite, mais notre travail en tant que programmeur consiste à créer une telle fonction de hachage à l'aide de laquelle le nombre de collisions est aussi faible que possible.

Une bonne fonction de hachage doit avoir les propriétés suivantes :

• Efficacement calculable.
• Doit répartir uniformément les clés (chaque position de table est également probable pour chacune).
• Devrait minimiser les collisions.
• Doit avoir un faible facteur de charge (le nombre d'éléments dans le tableau divisé par la taille du tableau).

3. Gestion des collisions : Puisqu'une fonction de hachage nous donne un petit nombre pour une grande clé, il est possible que deux clés donnent la même valeur. La situation dans laquelle une clé nouvellement insérée correspond à un emplacement déjà occupé dans la table de hachage est appelée collision et doit être gérée à l'aide d'une technique de gestion des collisions. Voici les façons de gérer les collisions :

• Chaînage : L'idée est de faire pointer chaque cellule de la table de hachage vers une liste chaînée d'enregistrements ayant la même valeur de fonction de hachage. Le chaînage est simple mais nécessite de la mémoire supplémentaire en dehors de la table.
• Adressage ouvert : En adressage ouvert, tous les éléments sont stockés dans la table de hachage elle-même. Chaque entrée de table contient soit un enregistrement, soit NIL. Lors de la recherche d'un élément, nous examinons les emplacements du tableau un par un jusqu'à ce que l'élément souhaité soit trouvé ou qu'il soit clair que l'élément n'est pas dans le tableau.

Implémentation avec exemple :

Étape 1: Créez une classe HashTable avec les propriétés initiales de table et de taille.

Étape 2: Ajoutez une fonction privée setKey(key) pour transformer les clés en indices.

Étape 3: Ajoutez les fonctions insert() et get() pour ajouter et accéder aux paires clé-valeur à partir de la table.

Étape 4: Ajoutez une fonction Remove() pour supprimer une clé de la table de hachage.

Exemple 1: Supposons que nous devions stocker 5 nombres 100,87,86,12,25 et 9 dans une table de hachage. Dans ce cas, nous allons créer une fonction setKey dans laquelle nous prendrons la valeur comme argument et la convertirons en index de la table de hachage. Ci-dessous la mise en œuvre.

Javascript

Sortir:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

En sortie ou montre que la table comporte 1 ou 3 espaces/index vides consécutifs.

Exemple 2 : Supposons que nous souhaitions stocker les numéros de contact d'une famille de 5 membres dans une table de hachage. Pour cela, nous allons créer une table de hachage de taille 10 et stocker les coordonnées. L'index sera défini à l'aide de la fonction privée setKey qui convertira le dernier chiffre du numéro de contact en index de la table de hachage.

Javascript

Sortir:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

En sortie ou montre que la table comporte 1 ou 3 espaces/index vides consécutifs.