En Python, un objet est considéré comme hashable s'il possède une valeur de hachage immuable et qu'il peut être comparé à d'autres objets.
Cela signifie que pour qu'un objet soit hashable, il doit implémenter les méthodes __hash__() et __eq__(), et son contenu ne doit pas changer au cours de son cycle de vie.
En termes simples, un objet hashable a un code de hachage fixe qui reste constant pendant toute la durée de vie de l'objet. Les types de données de base tels que les entiers (int), les flottants (float), les chaînes de caractères (str), et les tuples (tuple) (à condition que tous les éléments du tuple soient eux-mêmes hashables) sont des exemples d'objets hashables.
À quoi servent-ils ?
Les objets hashables sont particulièrement utiles dans les contextes où l'on a besoin de structures de données avec des opérations rapides de recherche et de comparaison.
En particulier, ils sont utilisés comme clés dans les dictionnaires (dict) et comme éléments dans les ensembles (set).
Ces structures de données dépendent de la fonction de hachage pour organiser les données de manière efficace et permettre un accès rapide.
Exemple avec les dictionnaires (dict)
Les clés des dictionnaires doivent être des objets hashables car les dictionnaires utilisent les codes de hachage des clés pour stocker et récupérer les valeurs associées de manière efficace.
# Exemples de clés hashables d = { 1: "integer", 3.14: "float", "key": "string", (1, 2): "tuple" } print(d[1]) # Sortie: integer print(d["key"]) # Sortie: string print(d[(1, 2)]) # Sortie: tuple
Exemple avec les ensembles (set)
Les éléments d'un ensemble doivent être hashables car les ensembles utilisent les codes de hachage pour vérifier l'unicité des éléments et pour les opérations rapides d'insertion et de recherche.
# Exemples d'éléments hashables s = {1, 3.14, "element", (1, 2)} print(1 in s) # Sortie: True print("element" in s) # Sortie: True print((1, 2) in s) # Sortie: True
Algorithmes de hachage
Les algorithmes de hachage sont des méthodes mathématiques qui transforment des données arbitraires (comme des chaînes de caractères) en une valeur fixe appelée condensat ou valeur de hachage (hash).
Comme on a pu le voir, ces valeurs sont utilisées pour indexer des objets dans des structures de données comme des dictionnaires et des ensembles.
Fonction de hashage
En Python, la fonction hash() est utilisée pour obtenir la valeur de hachage d'un objet hashable. Cette fonction utilise un algorithme de hachage pour produire un entier représentant l'objet.
>>> print(hash("docstring"))
6796903817329436193
Collisions de hachage
Les algorithmes de hachage ne sont pas parfaits. Deux objets différents peuvent avoir la même valeur de hachage, ce qui est appelé une collision.
Les dictionnaires et les ensembles utilisent des techniques pour gérer les collisions et maintenir des performances optimales.
hash(10) # Sortie: 10
hash(2+8) # Sortie: 10
hash(2**62 + 8) # Sortie: 10
Condensat
La valeur de hachage produite par un algorithme de hachage est également appelée condensat.
Cette valeur est utilisée pour identifier de manière unique des objets dans des structures de données.
Pourquoi sont-ils importants ?
Pour leur efficacité: l'utilisation des objets hashables permet de créer des structures de données très efficaces en termes de temps pour les opérations de recherche, d'insertion et de suppression. Cela est dû à la manière dont les valeurs de hachage permettent un accès direct aux emplacements de stockage.
Pour la comparabilité : les objets hashables doivent également être comparables. Cela signifie que deux objets hashables identiques doivent avoir le même code de hachage et être considérés comme égaux (__eq__ doit retourner True pour ces objets). Cette propriété est cruciale pour garantir la cohérence des opérations sur les ensembles et les dictionnaires.
