Qu'est-ce que le hachage? Fonctionnement des codes de hachage - avec des exemples

Introduction au hachage

Le hachage est conçu pour résoudre le problème de la nécessité de trouver ou de stocker efficacement un élément dans une collection.

Par exemple, si nous avons une liste de 10 000 mots en anglais et que nous voulons vérifier si un mot donné est dans la liste, il serait inefficace de comparer successivement le mot avec les 10 000 éléments jusqu'à ce que nous trouvions une correspondance. Même si la liste de mots est triée lexicographiquement, comme dans un dictionnaire, il vous faudra encore du temps pour trouver le mot que vous recherchez.

Le hachage est une technique pour rendre les choses plus efficaces en réduisant efficacement la recherche dès le départ.

Qu'est-ce que le hachage?

Le hachage signifie utiliser une fonction ou un algorithme pour mapper des données d'objet à une valeur entière représentative.

Ce soi-disant code de hachage (ou simplement hachage) peut ensuite être utilisé pour affiner notre recherche lors de la recherche de l'élément dans la carte.

En général, ces codes de hachage sont utilisés pour générer un index, auquel la valeur est stockée.

Comment fonctionne le hachage

Dans les tables de hachage, vous stockez les données sous forme de paires clé et valeur. La clé, qui sert à identifier les données, est donnée en entrée de la fonction de hachage. Le code de hachage, qui est un entier, est ensuite mappé à la taille fixe que nous avons.

Les tables de hachage doivent prendre en charge 3 fonctions.

  • insert (clé, valeur)
  • Obtenir la clé)
  • supprimer (clé)

À titre d'exemple purement pour nous aider à comprendre le concept, supposons que nous voulons mapper une liste de clés de chaîne à des valeurs de chaîne (par exemple, mapper une liste de pays à leurs capitales).

Disons que nous voulons stocker les données dans Table dans la carte.

Et supposons que notre fonction de hachage consiste simplement à prendre la longueur de la chaîne.

Pour simplifier, nous aurons deux tableaux: un pour nos clés et un pour les valeurs.

Donc, pour mettre un élément dans la table de hachage, nous calculons son code de hachage (dans ce cas, comptons simplement le nombre de caractères), puis mettons la clé et la valeur dans les tableaux à l'index correspondant.

Par exemple, Cuba a un code de hachage (longueur) de 4. Nous stockons donc Cuba en 4ème position dans le tableau des clés, et La Havane dans le 4ème index du tableau des valeurs, etc.

Maintenant, dans cet exemple spécifique, les choses fonctionnent assez bien. Notre tableau doit être suffisamment grand pour accueillir la chaîne la plus longue, mais dans ce cas, il ne s'agit que de 11 emplacements.

Nous perdons un peu d'espace car, par exemple, il n'y a pas de clés à 1 lettre dans nos données, ni de clés entre 8 et 10 lettres.

Mais dans ce cas, l'espace gaspillé n'est pas si grave non plus. Prendre la longueur d'une chaîne est agréable et rapide, tout comme le processus de recherche de la valeur associée à une clé donnée (certainement plus rapide que de faire jusqu'à cinq comparaisons de chaînes).

Mais que faisons-nous si notre ensemble de données a une chaîne de plus de 11 caractères?

Que faire si nous avons un autre mot avec 5 caractères, "Inde", et essayez de l'assigner à un index en utilisant notre fonction de hachage. L'indice 5 étant déjà occupé, nous devons nous demander quoi en faire. C'est ce qu'on appelle une collision.

Si notre ensemble de données avait une chaîne de mille caractères et que vous créez un tableau de mille indices pour stocker les données, cela entraînerait un gaspillage d'espace. Si nos clés étaient des mots aléatoires de l'anglais, où il y a tellement de mots de même longueur, utiliser la longueur comme fonction de hachage serait assez inutile.

Gestion des collisions

Deux méthodes de base sont utilisées pour gérer les collisions.

  1. Chaînage séparé
  2. Adressage ouvert

Chaînage séparé

La gestion des collisions de hachage par chaînage séparé utilise une structure de données supplémentaire, de préférence une liste liée pour l'allocation dynamique, dans des buckets. Dans notre exemple, lorsque nous ajoutons l'Inde à l'ensemble de données, il est ajouté à la liste chaînée stockée à l'index 5, alors notre table ressemblerait à ceci.

Pour trouver un élément, nous allons d'abord dans le seau, puis nous comparons les clés. C'est une méthode populaire, et si une liste de liens est utilisée, le hachage ne se remplit jamais. Le coût pour get(k)est en moyenne O(n)où n est le nombre de clés dans le compartiment, le nombre total de clés étant N.

Le problème avec le chaînage séparé est que la structure des données peut croître sans limites.

Adressage ouvert

L'adressage ouvert n'introduit aucune nouvelle structure de données. Si une collision se produit, nous recherchons la disponibilité dans le prochain spot généré par un algorithme. L'adressage ouvert est généralement utilisé lorsque l'espace de stockage est un processeur restreint, c'est-à-dire intégré. L'adressage ouvert n'est pas nécessairement plus rapide que le chaînage séparé.

Méthodes d'adressage ouvert

  • [Palpage linéaire
  • Sondage quadratique
  • Double hachage

Comment utiliser le hachage dans votre code.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:fusée:

Exécuter le code

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:fusée:

Exécuter le code

Plus d'informations sur le hachage

  • Le guide sans code des tables de hachage et de hachage
  • Comment implémenter une table de hachage simple en JavaScript
  • Explication des tables de hachage