Tabla de búsqueda para unashashable en Python

Necesito crear una asignación de objetos de mi propia clase personalizada (derivada de dict) a objetos de otra clase personalizada. Como yo lo veo hay dos maneras de hacer esto:

  1. Puedo hacer los objetos hashable. No estoy seguro de cómo haría esto. Sé que puedo implementar __hash__() pero no estoy seguro de cómo calcular realmente el hash (que debería ser un número entero).

  2. Dado que mis objetos se pueden comparar, puedo hacer una lista [(myobj, myotherobj)] y luego implementar una búsqueda que encuentre la tupla donde el primer elemento de la tupla es el mismo que la clave de búsqueda. Implementar esto es trivial (el número de objetos es pequeño) pero quiero evitar reinventar la rueda si ya existe algo así en la biblioteca estándar.

Me parece que querer buscar unashashable sería un problema común, así que asumo que alguien ya ha resuelto este problema. ¿Alguna sugerencia sobre cómo implementar __hash()__ para un objeto similar a un dictado o si existe alguna otra forma estándar de hacer tablas de búsqueda de elementos no lavables?

    Las asignaciones con objetos mutables como claves son generalmente difíciles. ¿Es eso realmente lo que quieres? Si considera que sus objetos son inmutables (no hay forma de imponer realmente la inmutabilidad en Python), o sabe que no se cambiarán mientras se usen como claves en un mapeo, puede implementar su propia función hash para ellos. varias maneras Por ejemplo, si su objeto solo tiene miembros de datos hashable, puede devolver el hash de una tupla de todos los miembros de datos como el hash de objetos.

    Si su objeto es similar a un dict, puede usar el hash de un conjunto de valores de todos los pares clave-valor.

     def __hash__(self): return hash(frozenset(self.iteritems())) 

    Esto solo funciona si todos los valores son hashables. Para guardar los recálculos de hash (que se realizarían en cada búsqueda), puede almacenar en caché el valor de hash y simplemente recalcularlo si se establece algún indicador sucio.

    Una solución simple parece ser lookup[id(myobj)] = myotherobj lugar de lookup[myobj] = myotherobj . ¿Algún comentario sobre este enfoque?

    Lo siguiente debería funcionar si no está almacenando ningún objeto adicional que no se pueda lavar en su clase personalizada:

     def __hash__(self): return hash(self.items()) 

    Aquí hay una implementación de un frozendict , tomada de http://code.activestate.com/recipes/414283/ :

     class frozendict(dict): def _blocked_attribute(obj): raise AttributeError, "A frozendict cannot be modified." _blocked_attribute = property(_blocked_attribute) __delitem__ = __setitem__ = clear = _blocked_attribute pop = popitem = setdefault = update = _blocked_attribute def __new__(cls, *args): new = dict.__new__(cls) dict.__init__(new, *args) return new def __init__(self, *args): pass def __hash__(self): try: return self._cached_hash except AttributeError: h = self._cached_hash = hash(tuple(sorted(self.items()))) return h def __repr__(self): return "frozendict(%s)" % dict.__repr__(self) 

    Yo reemplazaría la tuple(sorted(self.items())) por frozenset(self.iteritems()) como en la respuesta de Spacecowboy . Y considere agregar __slots__ = ("_cached_hash",) a la clase.