Objets mutables et hashables

Nous allons ici étudier deux propriétés fondamentales des objets en Python : leur mutabilité et leur hashabilité.

La première correspond à la capacité des objets à être altérés, modifiés.

La seconde est la possibilité pour un objet d’être hashé, c’est-à-dire d’en calculer un condensat qui permet entre-autres à l’objet d’être utilisé comme clef dans un dictionnaire.

Mutables

Un objet mutable est ainsi un objet qui peut être modifié, dont on peut changer les propriétés une fois qu’il a été défini. Une erreur courante est de confondre modification et réassignation.

La différence est facile à comprendre avec les listes. Les listes sont des objets mutables : une fois la liste instanciée, il est par exempe possible d’y insérer de nouveaux éléments.

1
2
3
4
>>> values = [0, 1, 2]
>>> values.append(3)
>>> values
[0, 1, 2, 3]

Le fonctionnement des variables en Python fait qu’il est possible d’avoir plusieurs noms (étiquettes) sur une même valeur. Le principe de mutabilité s’observe alors très bien.

1
2
3
4
5
6
>>> values = othervalues = [0, 1, 2]
>>> values.append(3)
>>> values
[0, 1, 2, 3]
>>> othervalues
[0, 1, 2, 3]

Sans que nous n’ayons explicitement touché à othervalues, sa valeur a changé. En effet, values et othervalues référencent un même objet. Un même objet mutable.

En revanche, la réassignation fait correspondre le nom de la variable à un nouvel objet, il n s’agit pas d’une modification de la valeur initiale.

1
2
3
4
5
6
>>> values = othervalues = [0, 1, 2]
>>> values = [0, 1, 2, 3] # réassignation de values
>>> values
[0, 1, 2, 3]
>>> othervalues
[0, 1, 2]

En Python, les objets de type bool, int, str, bytes, tuple, range et frozenset sont immutables. Tous les autres types, les listes, les dictionnaires, ou les instances de vos propres classes sont des objets mutables.

Comme nous l’avons vu, les objets mutables sont à prendre avec des pincettes, car leur valeur peut changer sans que nous ne l’ayons explicitement demandé. Cela peut arriver lorsqu’une valeur mutable est passée en argument à une fonction.

1
2
3
4
5
6
7
8
9
>>> def append_42(values):
...     values.append(42)
...     return values
...
>>> v = [1, 2, 3, 4]
>>> append_42(v)
[1, 2, 3, 4, 42]
>>> v
[1, 2, 3, 4, 42]

Cela ne pourra jamais arriver avec un tuple par exemple, qui est immutable et ne possède aucune méthode pour être altéré.

1
2
3
4
5
6
7
8
>>> def append_42(values):
...     return values + (42,)
...
>>> v = (1, 2, 3, 4)
>>> append_42(v)
(1, 2, 3, 4, 42)
>>> v
(1, 2, 3, 4)

Il n’est pas vraiment possible en Python de créer un nouveau type immutable. Cela peut être simulé en rendant les méthodes de modification/suppression inefficaces. Mais il est toujours possible de passer outre en appelant directement les méthodes d’une classe parente.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
>>> class ImmutableDeque(Deque):
...     def append(self, value):
...         raise TypeError('Object is read-only')
...     def insert(self, index, value):
...         raise TypeError('Object is read-only')
...     def __setitem__(self, key, value):
...         raise TypeError('Object is read-only')
...
>>> deque = ImmutableDeque()
>>> deque.append('foo')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in append
TypeError: Object is read-only
>>> Deque.append(deque, 'foo')
>>> deque[0]
'foo'

La seule manière sûre est d’hériter d’un autre type immutable, comme les namestuple qui héritent de tuple. Nous verrons plus loin dans ce cours comment cela est réalisable.

Égalité et identité

L’égalité et l’identité sont deux concepts dont la distinction est parfois confuse. Deux valeurs sont égales lorsqu’elles partagent un même état : par exemple, deux chaînes qui contiennent les mêmes caractères sont égales. Deux valeurs sont identiques lorsqu’elles sont une même instance, c’est-à-dire un même objet en mémoire.

En Python, on retrouve ces concepts sous les opérateurs == (égalité) et is (identité).

1
2
3
4
5
6
7
>>> [1, 2, 3] == [1, 2, 3]
True
>>> [1, 2, 3] is [1, 2, 3]
False
>>> values = [1, 2, 3]
>>> values is values
True

Leur différence est fondamentale pour les types mutables, puisque deux valeurs distinctes peuvent être égales à un moment et ne plus l’être par la suite (si l’une d’elles est modifiée). Deux valeurs identiques resteront à l’inverse égales, puisque les modifications seront perçues sur les deux variables.

1
2
3
4
5
6
7
8
>>> values1, values2 = [1, 2, 3], [1, 2, 3]
>>> values1 == values2
True
>>> values1 is values2
False
>>> values1.append(4)
>>> values1 == values2
False

1
2
3
4
5
6
7
8
>>> values1 = values2 = [1, 2, 3]
>>> values1 == values2
True
>>> values1 is values2
True
>>> values1.append(4)
>>> values1 == values2
True

L’opérateur d’égalité est surchargeable en Python, via la méthode spéciale __eq__ des objets. Il est en effet de la responsabilité du développeur de gérer la comparaison entre ses objets, et donc de déterminer quand ils sont égaux. Cette méthode reçoit en paramètre la valeur à laquelle l’objet est comparé, et retourne un booléen.

On peut imaginer une valeur qui sera égale à toute les autres, grâce à une méthoe __eq__ retournant toujours True.

1
2
3
4
5
6
7
8
9
>>> class AlwaysEqual:
...     def __eq__(self, value):
...         return True
...
>>> val = AlwaysEqual()
>>> val == 0
True
>>> 1 == val
True

L’opérateur d’identité testant si deux objets sont une même instance, il n’est bien sûr pas possibe de le surcharger. En absence de surcharge, l’opérateur d’égalité donnera la même résultat que l’identité.

Vous pouvez vous référer à ce chapitre du cours sur la POO en Python pour davantage d’informations sur la surcharge d’opérateurs.

Quel opérateur utiliser ?

Une question légitime à se poser suite à ces lignes est de savoir quel opérateur utiliser pour comparer nos valeurs. La réponse est que cela dépend des valeurs et des cas d’utilisation.

En règle générale, c’est l’opérateur d’égalité (==) qui est à utiliser. Quand nous comparons un nombre entré par l’utilisateur avec un nombre à deviner, nous ne cherchons pas à savoir s’ils sont un même objet, mais s’ils représentent la même chose.

L’opérateur is s’utilise principalement avec None. None est une valeur unique (singleton), il n’en existe qu’une instance. Quand on compare une valeur avec None, on vérifie qu’elle est None et non qu’elle vaut None.

Globalement, is s’utilise pour la comparaison avec des singletons, et == s’utilise pour le reste.

Hashables

Comme je le disais plus tôt, les objets hashables vont notamment servir pour les clefs des dictionnaires. Mais voyons tout d’abord à quoi correspond cette capacité.

Le condensat

En informatique, et plus particulièrement en cryptographie, on appelle condensat (hash) un nombre calculé depuis une valeur quelconque, unique et invariable pour cette valeur. Deux valeurs égales partageront un même hash, deux valeurs différentes auront dans la mesure du possible des hash différents.

En effet, le condensat est généralement un nombre de taille fixe (64 bits par exemple), il existe donc un nombre limité de hashs pour un nombre infini de valeurs. Deux valeurs différentes pourront alors avoir un même condensat, c’est ce que l’on appelle une collision. Les collisions sont plus ou moins fréquentes selon les algorithmes de hashage. En cela, l’égalité entre hashs ne doit jamais remplacer l’égalité entre les valeurs, elle n’est qu’une étape préliminaire qui peut servir à optimiser des calculs.

La fonction hash

En Python, on peut calculer le condensat d’un objet à l’aide de la fonction hash.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>> hash(10)
10
>>> hash(2**61 + 9) # collision
10
>>> hash('toto')
-7475273891964572862
>>> hash((1, 2, 3))
2528502973977326415
>>> hash([1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Ce dernier exemple nous montre que les listes ne sont pas hashables. Pourquoi ? On a vu que le hash était invariable, mais il doit pourtant correspondre à la valeur.

Or, en modifiant une liste, le condensat calculé auparavant deviendrait invalide. Il est donc impossible de hasher les listes. Il en est de même pour les dictionnaires et les ensembles (set). Tous les autres types d’objets sont par défaut hashables.

On remarque une certaine corrélation entre types mutables et hashables. En effet, il est plus facile d’assurer l’invariabilité du condensat quand l’objet est lui-même immutable. Pour les objets mutables, le hash n’est possible que si la modification n’altère pas l’égalité entre deux objets, c’est-à-dire que deux objets égaux le resteront même si l’un est modifié.

Il faut aussi garder à l’esprit que des types immutables peuvent contenir des mutables. Par exemple une liste dans un tuple. Dans ce genre de cas, la non-hashabilité des valeurs contenues rend non-hashable le conteneur.

1
2
3
4
5
6
7
8
>>> t = ((0, 1), (2, 3))
>>> hash(t)
8323144716662114087
>>> t = ((0, 1), [2, 3])
>>> hash(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

À quoi servent-ils ?

Je parle depuis le début de clefs de dictionnaires, nous allons maintenant voir pourquoi les dictionnaires utilisent des condensats.

Les dictionnaires, d’ailleurs appelés tables de hashage dans certains langages, sont des structures qui doivent permettre un accès rapide aux éléments. Ainsi, ils ne peuvent pas être une simple liste de couples clef/valeur, qui serait parcourue chaque fois que l’on demande un élément.

À l’aide des hash, les dictionnaires disposent les éléments tels que dans un tableau et offrent un accès direct à la majorité d’entre eux.

Outre les dictionnaires, ils sont aussi utilisés dans les set, ensembles non ordonnés de valeurs uniques.

On remarque facilement que les objets non-hashables ne peuvent être utilisés en tant que clefs de dictionnaires ou dans un ensemble.

1
2
3
4
5
6
7
8
>>> {[0]: 'foo'}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> {{'foo': 'bar'}}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'

Plus généralement, les hash peuvent être utilisés pour optimiser le test d’égalité entre deux objets. Le hash étant invariable, il est possible de ne le calculer qu’une fois par objet (en stockant sa valeur).

Ainsi, lors d’un test d’égalité, on peut facilement dire que les objets sont différents, si les hash le sont. L’inverse n’est pas vrai à cause des collisions : deux objets différents peuvent avoir un même hash. Le test d’égalité proprement dit (appel à la méthode __eq__) doit donc toujours être réalisé si les hash sont égaux.

Implémentation

Les types de votre création sont par défaut hashables, puisque l’égalité entre objets vaut l’idendité. La question de la hashabilité ne se pose donc que si vous surchargez l’opérateur __eq__.

Dans ce cas, il convient normalement de vous occuper aussi de la méthode spéciale __hash__. C’est cette méthode qui est appelée par la fonction hash pour calculer le condensat d’un objet.

Il est aussi possible d’assigner None à __hash__ afin de rendre l’objet non-hashable. Python le fait par défaut lorsque nous surchargeons l’opérateur __eq__.

Pour reprendre la classe AlwaysEqual définie précédemment :

1
2
3
4
5
6
7
>>> val = AlwaysEqual()
>>> hash(val)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'AlwaysEqual'
>>> print(val.__hash__)
None

Si toutefois vous souhaitez redéfinir la méthode __hash__, il vous faut respecter les quelques règles énoncées plus haut.

  • L’invariabilité du hash ;
  • L’égalité entre deux hashs de valeurs égales.

Ces conditions état plus faciles à respecter pour des valeurs immutables.

Notons enfin que le résultat de la méthode __hash__ est tronqué par la fonction hash, afin de tenir sur un nombre fixe de bits.

Pour plus d’informations sur cette méthode __hash__ : https://docs.python.org/3/reference/datamodel.html#object.__hash__.

TP : Égalité entre listes

Nous allons maintenant nous intéresser à l’implémentation de l’opérateur d’égalité entre listes. Nos listes, mutables, deviendront par conséquent non-hashables. Nous reviendrons vers la fin de ce cours sur l’implémentation de listes immutables.

L’opérateur d’égalité correspond donc à la méthode spéciale __eq__, recevant en paramètre l’objet auquel self est comparé. La méthode retourne ensuite True si les objets sont égaux, False s’ils sont différents, et NotImplemented si la comparaison ne peut être faite.

NotImplemented est une facilité de Python pour gérer les opérateurs binaires. En effet, dans une égalité a == b par exemple, on ne peut pas savoir lequel de a ou b redéfinit la méthode __eq__. L’interpréteur va alors tester en premier d’appeler la méthode de a :

  • Si la méthode retourne True, les objets sont égaux ;
  • Si elle retourne False, ils sont différents ;
  • Si elle retourne NotImplemented, alors l’interpréteur appellera la méthode __eq__ de b pour déterminer le résultat ;
  • Si les deux méthodes retournent NotImplemented, les objets sont différents.

Dans notre méthode, nous allons donc premièrement vérifier le type du paramètre. S’il n’est pas du type attendu (Deque), nous retournerons NotImplemented.

Nous comparerons ensuite la taille des listes, si la taille diffère, les listes sont nécessairement différentes. Dans l’idéal, nous devrions éviter cette comparaison car elle est coûteuse (elle nécessite de parcourir entièrement chacune des listes), mais nous pouvons la conserver dans le cadre de l’exercice.

Enfin, nous itérerons simultanément sur nos deux listes pour vérifier que tous les éléments sont égaux.

1
2
3
4
5
6
7
8
9
def __eq__(self, other):
    if not isinstance(other, Deque):
        return NotImplemented
    if len(self) != len(other):
        return False
    for elem1, elem2 in zip(self, other):
        if elem1 != elem2:
            return False
    return True

C’est l’heure du test !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
>>> d = Deque([0, 1])
>>> d == Deque([0, 1])
True
>>> d == Deque([0, 1, 2])
False
>>> d == Deque([1, 2])
False
>>> d == 0
False
>>> d.append(2)
>>> d == Deque([0, 1])
False
>>> d == Deque([0, 1, 2])
True

Et comme nous pouvons le constater, notre Deque a perdu son pouvoir d’hashabilité.

1
2
3
4
>>> hash(d)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'Deque'

Nous retrouvons ici les traditionnelles références vers la documentation officielle.