Pourquoi les ensembles Python ne sont-ils pas hachables ?

Question

Je suis tombé sur un article de blog expliquant comment implémenter une fonction powerset en Python. J'ai donc essayé de le faire à ma façon, et j'ai découvert que Python ne peut apparemment pas avoir un ensemble d'ensembles, puisque set n'est pas hachable. C'est ennuyeux, puisque la définition d'un powerset est qu'il s'agit d'un ensemble d'ensembles, et je voulais l'implémenter en utilisant des opérations d'ensembles réelles.

>>> set([ set() ])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'

Y a-t-il une bonne raison pour que les ensembles Python ne soient pas hachables ?

Answer 1

En général, seuls les objets immuables sont hachables en Python. La variante immuable de set() -- frozenset() -- est hachable.

Answer 2

Parce qu'ils sont mutables.

S'ils étaient hachables, un hachage pourrait devenir silencieusement "invalide", ce qui rendrait le hachage pratiquement inutile.

Answer 3

Extrait de la documentation Python :

hachable
A possède une valeur de hachage qui ne change jamais pendant sa durée de vie (il faut dièse (), et peuvent être compa eq () ou cmp () méthode). Les objets hachables dont la comparaison est égale doivent avoir la même valeur de hachage.

La possibilité de hachage rend un objet utilisable comme une clé de dictionnaire et un membre d'un ensemble, car ces structures de données utilisent la valeur de hachage en interne.

Tous les objets intégrés immuables de Python Python sont hachables, alors qu'aucun conteneur mutable (comme les listes ou les dictionnaires) ne le sont. Les objets qui sont instances de classes définies par l'utilisateur sont hachables par défaut ; ils sont tous comparables inégales, et leur valeur de hachage est leur id().

Answer 4

Si cela peut vous aider... si vous avez vraiment besoin de convertir des éléments non hachables en équivalents hachables pour une raison quelconque, vous pouvez faire quelque chose comme ceci :

from collections import Hashable, MutableSet, MutableSequence, MutableMapping

def make_hashdict(value):
    """
    Inspired by https://stackoverflow.com/questions/1151658/python-hashable-dicts
     - with the added bonus that it inherits from the dict type of value
       so OrderedDict's maintain their order and other subclasses of dict() maintain their attributes
    """
    map_type = type(value)

    class HashableDict(map_type):
        def __init__(self, *args, **kwargs):
            super(HashableDict, self).__init__(*args, **kwargs)
        def __hash__(self):
            return hash(tuple(sorted(self.items())))

    hashDict = HashableDict(value)

    return hashDict

def make_hashable(value):
    if not isinstance(value, Hashable):
        if isinstance(value, MutableSet):
            value = frozenset(value)
        elif isinstance(value, MutableSequence):
            value = tuple(value)
        elif isinstance(value, MutableMapping):
            value = make_hashdict(value)

        return value

my_set = set()
my_set.add(make_hashable(['a', 'list']))
my_set.add(make_hashable({'a': 1, 'dict': 2}))
my_set.add(make_hashable({'a', 'new', 'set'}))

print my_set

Mon implémentation de HashableDict est l'exemple le plus simple et le moins rigoureux de aquí . Si vous avez besoin d'un HashableDict plus avancé qui supporte le décapage et d'autres choses, consultez les nombreuses autres implémentations. Dans ma version ci-dessus, je voulais conserver la classe dict originale, préservant ainsi l'ordre des OrderedDicts. J'utilise également AttrDict de aquí pour un accès de type attribut.

Mon exemple ci-dessus ne fait en aucun cas autorité, il s'agit simplement de ma solution à un problème similaire où j'avais besoin de stocker certaines choses dans un ensemble et où je devais d'abord les "hacher".