Un guide pour les cartes de hachage de Python

Lorsque les praticiens des données parlent aujourd'hui de stockage des données, ils font la plupart du temps référence à l'endroit où les données sont stockées, qu'il s'agisse de fichiers locaux, de bases de données SQL ou NoSQL, ou encore du cloud. Cependant, un autre aspect important lié au stockage des données est la manière dont les données sont stockées.

Le mode de stockage des données se situe souvent à un niveau inférieur, au cœur même des langages de programmation. Il s'agit de la conception des outils utilisés par les praticiens des données plutôt que de la manière d'utiliser ces outils. Pourtant, il est essentiel pour les professionnels des données de savoir comment les données sont stockées afin de comprendre les mécanismes sous-jacents qui rendent leur travail possible. De plus, ces connaissances peuvent les aider à prendre de meilleures décisions pour améliorer les performances informatiques.

Dans cet article, nous parlerons des hashmaps. Une table de hachage est une structure de données qui exploite les techniques de hachage pour stocker des données de manière associative. Les Hashmaps sont des structures de données optimisées qui permettent des opérations de données plus rapides, notamment l'insertion, la suppression et la recherche.

De nombreux langages de programmation modernes, tels que Python, Java et C++, prennent en charge les cartes de hachage. En Python, les hashmaps sont mis en œuvre par le biais de dictionnaires, une structure de données largement utilisée que vous connaissez sans doute. Dans les sections suivantes, nous aborderons les bases des dictionnaires, leur fonctionnement et la manière de les mettre en œuvre à l'aide de différents packages Python.

Qu'est-ce qu'un Hashmap ?

Pour définir une table de hachage, nous devons d'abord comprendre ce qu'est le hachage. Le hachage est le processus de transformation d'une clé donnée ou d'une chaîne de caractères en une autre valeur. Le résultat est normalement une valeur plus courte, de longueur fixe, qui facilite le calcul par rapport à la clé d'origine.

Les cartes de hachage, également connues sous le nom de tables de hachage, représentent l'une des implémentations les plus courantes du hachage. Les Hashmaps stockent des paires clé-valeur (par exemple, l'identifiant et le nom d'un employé) dans une liste accessible par son index.

L'idée derrière les hashmaps est de distribuer les entrées (paires clé/valeur) dans un tableau de buckets. Compte tenu d'une clé, une fonction de hachage calcule un index distinct qui indique où l'entrée peut être trouvée. L'utilisation d'un index au lieu de la clé d'origine rend les hashmaps particulièrement bien adaptés à de multiples opérations sur les données, notamment l'insertion, la suppression et la recherche de données.

Fonctionnement d'une table de concordance.

Pour calculer la valeur de hachage, ou simplement le hachage, une fonction de hachage génère de nouvelles valeurs selon un algorithme de hachage mathématique. Les paires clé-valeur étant, en théorie, illimitées, la fonction de hachage mappera les clés en fonction d'une taille de tableau donnée.

Il existe plusieurs fonctions de hachage, chacune ayant ses avantages et ses inconvénients. L'objectif principal d'une fonction de hachage est de toujours renvoyer la même valeur pour la même entrée.

Les plus courantes sont les suivantes :

• Méthode de division. C'est le moyen le plus simple et le plus rapide de calculer les valeurs de hachage. Pour ce faire, on divise la clé par la taille du tableau, puis on utilise le reste comme hachage.
• Méthode du carré moyen. Il trouvera le carré de la clé donnée, puis prendra les chiffres du milieu et les utilisera comme index de l'élément.
• Méthode de multiplication. Il définit l'indice de hachage à partir de la partie fractionnaire de la multiplication de la clé par un grand nombre réel.
• Méthode de pliage. La clé est d'abord divisée en tableaux de taille égale, le résultat est additionné et le résultat est divisé par la taille du tableau. Le hachage est le rappel.

Hashmap en Python

Python implémente les hashmaps par le biais du type de données intégré dictionnaire. Comme les hashmaps, les dictionnaires stockent les données sous forme de paires {clé:valeur}. Une fois que vous avez créé le dictionnaire (voir la section suivante), Python applique une fonction de hachage pratique sous le capot pour calculer le hachage de chaque clé.

Les dictionnaires Python présentent les caractéristiques suivantes :

• Les dictionnaires sont mutables. Cela signifie que nous pouvons modifier, ajouter ou supprimer des éléments après la création du dictionnaire.
• Les éléments sont ordonnés. Dans Python 3.6 et les versions antérieures, les dictionnaires n'étaient pas ordonnés, ce qui signifie que les éléments n'avaient pas d'ordre défini. Cependant, suite à la sortie de Python 3.7, les dictionnaires sont devenus à ordre préservé. Désormais, lorsque vous créerez un dictionnaire Python, les clés suivront l'ordre indiqué dans le code source. Pour en savoir plus sur les raisons de ce changement, lisez cette note de Raymond Hettinger, l'un des principaux développeurs de Python.
• Les clés sont immuables. Cela signifie que les clés sont toujours des types de données qui ne peuvent pas être modifiés. En d'autres termes, les dictionnaires n'autorisent que les types de données pouvant être hachés, comme les chaînes de caractères, les nombres et les tuples. Au contraire, les clés ne peuvent jamais être un type de données mutables, comme une liste.
• Les clés sont uniques. Les clés sont uniques dans un dictionnaire et ne peuvent pas être dupliquées dans un dictionnaire. S'il est utilisé plus d'une fois, les entrées suivantes écraseront la valeur précédente.

Si vous vous êtes déjà interrogé sur les différences entre les hashmaps et les dictionnaires, la réponse est simple. Un dictionnaire est l'implémentation native des tables de hachage de Python. Alors qu'une table de hachage est une structure de données qui peut être créée à l'aide de plusieurs techniques de hachage, un dictionnaire est une table de hachage particulière, basée sur Python, dont la conception et le comportement sont spécifiés dans la classe dict de Python.

Comment utiliser les dictionnaires Python

Voyons quelques-unes des opérations les plus courantes du dictionnaire. Pour en savoir plus sur l'utilisation des dictionnaires, consultez notre tutoriel sur les dictionnaires Python.

Création d'un dictionnaire

La création de dictionnaires en Python est assez simple. Il vous suffit d'utiliser des accolades et d'insérer les paires clé-valeur séparées par des virgules. Vous pouvez également utiliser la fonction intégrée dict(). Créons un dictionnaire qui associe les capitales aux pays :

# Create dictionary
dictionary_capitals = {'Madrid": 'Spain", 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Pour imprimer le contenu du dictionnaire :

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Il est important de se rappeler qu'une clé doit être unique dans un dictionnaire ; les doublons ne sont pas autorisés. Cependant, en cas de duplication de clés, plutôt que d'afficher une erreur, Python considérera la dernière instance de la clé comme valide et ignorera simplement la première paire clé-valeur. Voyez par vous-même :

dictionary_capitals = {'Madrid': 'China', 'Lisboa': 'Portugal', 
                       'London': 'United Kingdom','Madrid':'Spain'}

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Recherche dans un dictionnaire

Pour rechercher des informations dans notre dictionnaire, nous devons spécifier la clé entre parenthèses, et Python renverra la valeur associée, comme suit :

# Search for data
dictionary_capitals['Madrid']

'Spain'

Si vous essayez d'accéder à une clé qui n'est pas présente dans le dictionnaire, Python lancera une erreur. Pour éviter cela, vous pouvez accéder aux clés en utilisant la méthode .get(). Dans le cas d'une clé inexistante, la valeur renvoyée sera simplement None :

print(dictionary_capitals.get('Prague'))

None

Ajouter et supprimer des valeurs dans un dictionnaire

Ajoutons une nouvelle paire capitale-pays :

# Create a new key-value pair
dictionary_capitals['Berlin'] = 'Italy'

La même syntaxe peut être utilisée pour mettre à jour la valeur associée à une clé. Fixons la valeur associée à Berlin :

# Update the value of a key
dictionary_capitals['Berlin'] = 'Germany'

Supprimons maintenant l'une des paires de notre dictionnaire

# Delete key-value pair
del dictionary_capitals['Lisboa']

print(dictionary_capitals)

{'Madrid': 'Spain', 'London': 'United Kingdom', 'Berlin': 'Germany'}

Si vous souhaitez supprimer toutes les paires clé-valeur du dictionnaire, vous pouvez utiliser la méthode .clear():

dictionary_capitals.clear()

Passer en revue les dictionnaires

Si vous souhaitez récupérer toutes les paires clé-valeur, utilisez la méthode .items(), et Python récupérera une liste itérable de tuples :

dictionary_capitals.items()

dict_items([('Madrid', 'Spain'), ('London', 'United Kingdom'), ('Berlin', 'Germany')])

# Iterate over key-value pairs
for key, value in dictionary_capitals.items():
    print('the capital of {} is {}'.format(value, key))

the capital of Spain is Madrid
the capital of United Kingdom is London
the capital of Germany is Berlin

De même, si vous souhaitez récupérer une liste itérable avec les clés et les valeurs, vous pouvez utiliser les méthodes .keys() et .values(), respectivement :

dictionary_capitals.keys()

dict_keys(['Madrid', 'London', 'Berlin'])

for key in dictionary_capitals.keys():
    print(key.upper())

MADRID
LONDON
BERLIN

dictionary_capitals.values()

dict_values(['Spain', 'United Kingdom', 'Germany'])

for value in dictionary_capitals.values():
    print(value.upper())

SPAIN
UNITED KINGDOM
GERMANY

Applications concrètes des cartes de hachage

Les cartes de hachage sont des structures de données puissantes utilisées presque partout dans le monde numérique. Vous trouverez ci-dessous une liste d'applications réelles des cartes de hachage :

• Indexation de la base de données. Les cartes de hachage sont souvent utilisées pour l'indexation et la recherche de volumes massifs de données. Les navigateurs web courants utilisent des hashmaps pour stocker les pages web indexées.
• Gestion du cache. Les systèmes d'exploitation modernes utilisent des hashmaps pour organiser la mémoire cache afin de permettre un accès rapide aux informations fréquemment utilisées.
• Cryptographie. Les cartes de hachage jouent un rôle essentiel dans le domaine de la cryptographie. Les algorithmes cryptographiques s'appuient sur les cartes de hachage pour assurer l'intégrité et la validation des données et sécuriser les transactions sur les réseaux.
• Blockchain. Les cartes de hachage sont au cœur de la blockchain. Chaque fois qu'une transaction a lieu dans le réseau, les données de cette transaction sont prises en compte par la fonction de hachage, qui produit alors un résultat unique. Chaque bloc de la blockchain porte le hachage du bloc précédent, formant ainsi une chaîne de blocs.

Meilleures pratiques et erreurs courantes de Hashmap

Les cartes de hachage sont des structures de données incroyablement polyvalentes et efficaces. Cependant, elles s'accompagnent également de problèmes et de limites. Pour résoudre les problèmes courants liés aux cartes de hachage, il est important de garder à l'esprit certaines considérations et bonnes pratiques.

Les clés doivent être immuables

C'est logique : si le contenu de la clé change, la fonction de hachage renverra un hachage différent, et Python ne pourra donc pas retrouver la valeur associée à la clé.

Traiter les collisions hashmap

Le hachage ne fonctionne que si chaque élément correspond à un emplacement unique dans le tableau de hachage. Mais il arrive que les fonctions de hachage renvoient la même sortie pour des entrées différentes. Par exemple, si vous utilisez une fonction de hachage de division, différents entiers peuvent avoir la même fonction de hachage (ils peuvent renvoyer le même reste lors de l'application du module de division), ce qui crée un problème appelé collision. Les collisions doivent être résolues et plusieurs techniques existent. Heureusement, dans le cas des dictionnaires, Python gère les collisions potentielles sous le capot.

Comprendre le facteur de charge

Le facteur de charge est défini comme le rapport entre le nombre d'éléments du tableau et le nombre total de godets. Il s'agit d'une mesure permettant d'estimer le degré de distribution des données. En règle générale, plus les données sont réparties uniformément, moins il y a de risques de collisions. Là encore, dans le cas des dictionnaires, Python adapte automatiquement la taille du tableau en cas d'insertion ou de suppression de nouvelles paires clé-valeur.

Soyez conscient de la performance

Une bonne fonction de hachage minimise le nombre de collisions, est facile à calculer et répartit uniformément les éléments dans le tableau de hachage. Cela peut se faire en augmentant la taille du tableau ou la complexité de la fonction de hachage. Bien que cette méthode soit pratique pour un petit nombre d'éléments, elle n'est pas réalisable lorsque le nombre d'éléments possibles est élevé, car elle se traduirait par des cartes de hachage gourmandes en mémoire et moins efficaces.

Les dictionnaires sont-ils ce dont vous avez besoin ?

Les dictionnaires sont excellents, mais d'autres structures de données peuvent être plus adaptées à vos données et à vos besoins spécifiques. En fin de compte, les dictionnaires ne prennent pas en charge les opérations courantes, telles que l'indexation, le découpage et la concaténation, ce qui les rend moins flexibles et plus difficiles à utiliser dans certains scénarios.

Implémentations alternatives de la table de hachage Python

Comme nous l'avons déjà mentionné, Python implémente les hashmaps par le biais de dictionnaires intégrés. Cependant, il est important de noter qu'il existe d'autres outils Python natifs, ainsi que des bibliothèques tierces, pour exploiter la puissance des hashmaps.

Voyons quelques-uns des exemples les plus courants.

Défauts

Chaque fois que vous essayez d'accéder à une clé qui n'est pas présente dans votre dictionnaire, Python renvoie une KeyError. Pour éviter cela, vous pouvez rechercher des informations à l'aide de la méthode .get(). Cependant, une façon optimisée de le faire est d'utiliser un Defaultdict, disponible dans les collections de modules. Les dictionnaires par défaut et les dictionnaires sont presque identiques. La seule différence est que defaultdict ne soulève jamais d'erreur car il fournit une valeur par défaut pour les clés inexistantes.

from collections import defaultdict 

# Defining the dict 
capitals = defaultdict(lambda: "The key doesn't exist") 
capitals['Madrid'] = 'Spain'
capitals['Lisboa'] = 'Portugal'
  
print(capitals['Madrid']) 
print(capitals['Lisboa']) 
print(capitals['Ankara']) 

Spain
Portugal
The key doesn't exist 

Compteur

Counter est une sous-classe de dictionnaire Python spécifiquement conçue pour compter les objets hachables. Il s'agit d'un dictionnaire dans lequel les éléments sont stockés en tant que clés et leur nombre en tant que valeurs.

Il existe plusieurs façons d'initialiser Counter :

• Par une séquence d'éléments.
• Par clés et nombres dans un dictionnaire.
• Utilisation de la correspondance nom:valeur.

from collections import Counter 

# a new counter from an iterable
c1 = Counter(['aaa','bbb','aaa','ccc','ccc','aaa'])
# a new counter from a mapping
c2 = Counter({'red': 4, 'blue': 2})     
# a new counter from keyword args
c3 = Counter(cats=4, dogs=8)       
# print results
print(c1)
print(c2)
print(c3)

Counter({'aaa': 3, 'ccc': 2, 'bbb': 1})
Counter({'red': 4, 'blue': 2})
Counter({'dogs': 8, 'cats': 4})

La classe des compteurs est accompagnée d'une série de méthodes pratiques permettant d'effectuer des calculs courants.

print('keys of the counter: ', c3.keys())
print('values of the counter: ',c3.values()) 
print('list with all elements: ', list(c3.elements())) 
print('number of elements: ', c3.total()) # number elements
print('2 most common occurrences: ', c3.most_common(2)) # 2 most common occurrences 

dict_keys(['cats', 'dogs'])
dict_values([4, 8])
['cats', 'cats', 'cats', 'cats', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs']
12
[('dogs', 8), ('cats', 4)]

Méthodes de hachage Scikit-learn

Scikit-learn, également connu sous le nom de sklearn, est une bibliothèque d'apprentissage automatique Python robuste et open-source. Il a été créé pour aider à simplifier le processus de mise en œuvre de l'apprentissage automatique et des modèles statistiques en Python.

Sklearn propose plusieurs méthodes de hachage qui peuvent s'avérer très utiles pour les processus d'ingénierie des fonctionnalités.

L'une des plus courantes est la méthode CountVectorizer. Il est utilisé pour transformer un texte donné en un vecteur basé sur la fréquence de chaque mot apparaissant dans l'ensemble du texte. CountVectorized est particulièrement utile dans les contextes d'analyse de texte.

from sklearn.feature_extraction.text import CountVectorizer
 
documents = ["Welcome to this new DataCamp Python course",
            "Welcome to this new DataCamp R skill track",
            "Welcome to this new DataCamp Data Analyst career track"]
 
# Create a Vectorizer Object
vectorizer = CountVectorizer()

X = vectorizer.fit_transform(documents)

# print unique values 
print('unique words: ', vectorizer.get_feature_names_out())


#print sparse matrix with word frequency
pd.DataFrame(X.toarray(), columns = vectorizer.get_feature_names_out())

unique words:  ['analyst' 'career' 'course' 'data' 'datacamp' 'new' 'python' 'skill' 'this' 'to' 'track' 'welcome']

Il existe d'autres méthodes de hachage dans sklearn, notamment FeatureHasher et DictVectorizer. Notre cours School Budgeting with Machine Learning in Python est un excellent exemple où vous pouvez apprendre comment ils fonctionnent en pratique.

Conclusion

Félicitations pour avoir terminé ce tutoriel sur les cartes de hachage. Nous espérons que vous avez maintenant une meilleure compréhension des hashmaps et des dictionnaires Python. Si vous souhaitez en savoir plus sur les dictionnaires et leur utilisation dans des scénarios réels, nous vous recommandons vivement de lire notre tutoriel dédié aux dictionnaires Python, ainsi que notre tutoriel sur la compréhension des dictionnaires Python.

Enfin, si vous débutez en Python et souhaitez en savoir plus, suivez le cours Introduction à la science des données en Python de DataCamp et consultez notre tutoriel Python pour les débutants.