Utilisation d'objets Python non hachables comme clés dans les dictionnaires

Question

Python ne permet pas aux objets non hachables d'être utilisés comme clés dans d'autres dictionnaires. Comme l'a souligné Andrey Vlasovskikh, il existe une solution de contournement intéressante pour le cas particulier de l'utilisation de dictionnaires non imbriqués comme clés :

frozenset(a.items())#Can be put in the dictionary instead

Existe-t-il une méthode permettant d'utiliser des objets arbitraires comme clés dans les dictionnaires ?

Ejemplo :

Comment cela pourrait-il être utilisé comme une clé ?

{"a":1, "b":{"c":10}}

Il est extrêmement rare que vous ayez à utiliser quelque chose comme cela dans votre code. Si vous pensez que c'est le cas, envisagez d'abord de modifier votre modèle de données.

Cas d'utilisation exact

Le cas d'utilisation est la mise en cache des appels à une fonction arbitraire de mot-clé seulement. Chaque clé du dictionnaire est une chaîne de caractères (le nom de l'argument) et les objets peuvent être assez compliqués, consistant en des dictionnaires, listes, tuples, etc. superposés.

Problèmes connexes

Ce sous-problème a été séparé de celui de la le problème ici . Les solutions proposées ici traitent du cas où les dictionnaires ne sont pas superposés.

Answer 1

Basé sur la solution de Chris Lutz à nouveau.

import collections

def hashable(obj):
    if isinstance(obj, collections.Hashable):
        items = obj
    elif isinstance(obj, collections.Mapping):
        items = frozenset((k, hashable(v)) for k, v in obj.iteritems())
    elif isinstance(obj, collections.Iterable):
        items = tuple(hashable(item) for item in obj)
    else:
        raise TypeError(type(obj))

    return items

Answer 2

Ne le fais pas. Je suis d'accord avec le commentaire d'Andreys sur la question précédente : cela n'a pas de sens d'avoir des dictionnaires comme clés, et surtout pas des dictionnaires imbriqués. Votre modèle de données est manifestement assez complexe, et les dictionnaires ne sont probablement pas la bonne réponse. Vous devriez plutôt essayer l'OO.

Answer 3

Basé sur la solution de Chris Lutz. Notez que cette solution ne gère pas les objets qui sont modifiés par itération, comme les flux, ni les cycles.

import collections

def make_hashable(obj):
    """WARNING: This function only works on a limited subset of objects
    Make a range of objects hashable. 
    Accepts embedded dictionaries, lists or tuples (including namedtuples)"""
    if isinstance(obj, collections.Hashable):
        #Fine to be hashed without any changes
        return obj
    elif isinstance(obj, collections.Mapping):
        #Convert into a frozenset instead
        items=list(obj.items())
        for i, item in enumerate(items):
                items[i]=make_hashable(item)
        return frozenset(items)
    elif isinstance(obj, collections.Iterable):
        #Convert into a tuple instead
        ret=[type(obj)]
        for i, item in enumerate(obj):
                ret.append(make_hashable(item))
        return tuple(ret)
    #Use the id of the object
    return id(obj)

Answer 4

Si vous devez vraiment le faire, rendez vos objets hachables. Sous-classez ce que vous voulez mettre comme clé, et fournissez une fonction __hash__ qui renvoie une clé unique à cet objet.

Pour illustrer :

>>> ("a",).__hash__()
986073539
>>> {'a': 'b'}.__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable

Si votre hachage n'est pas suffisamment unique, vous obtiendrez des collisions. Cela peut aussi être lent.

Answer 5

Je suis en total désaccord avec les commentaires et les réponses qui disent que cela ne devrait pas être fait pour des raisons de pureté du modèle de données.

Un dictionnaire associe un objet à un autre objet en utilisant le premier comme clé. Les dictionnaires ne peuvent pas être utilisés comme clés car ils ne sont pas hachables. Cela ne rend pas moins utile/pratique/nécessaire l'association de dictionnaires à d'autres objets.

Si je comprends bien le système de liaison Python, vous pouvez lier n'importe quel dictionnaire à un certain nombre de variables (ou l'inverse, selon votre terminologie), ce qui signifie que ces variables connaissent toutes le même "pointeur" unique vers ce dictionnaire. Ne serait-il pas possible d'utiliser cet identifiant comme clé de hachage ? Si votre modèle de données garantit/explique que vous ne pouvez pas avoir deux dictionnaires avec le même contenu utilisés comme clés, cela me semble être une technique sûre.

Je dois ajouter que je n'ai pas la moindre idée de la manière dont cela peut/doit être fait.

Je ne sais pas exactement si cela doit être une réponse ou un commentaire. Veuillez me corriger si nécessaire.