Python中不可哈希对象的查找表

Question

我需要创建一个映射，把我自己定义的类（这个类是从字典派生的）中的对象，映射到另一个自定义类的对象上。根据我的理解，有两种方法可以做到这一点：

1. 我可以让这些对象可以被哈希。可是我不太确定该怎么做。我知道可以实现 __hash__() 这个方法，但我不太清楚具体该如何计算哈希值（哈希值应该是一个整数）。

2. 因为我的对象可以进行比较，所以我可以创建一个列表，比如 [(我的对象, 另一个对象)]，然后实现一个查找功能，找到那个元组，其中元组的第一个元素和查找的键是一样的。实现这个功能其实很简单（因为对象的数量不多），但我想避免重复造轮子，如果标准库里已经有类似的东西就好了。

我觉得想要查找不可哈希的对象应该是一个常见的问题，所以我想应该有人已经解决了这个问题。有没有什么建议，关于如何为类似字典的对象实现 __hash()__，或者有没有其他标准的方法来制作不可哈希对象的查找表？

Answer 1

如果你的自定义类里面没有存储任何额外的不能被哈希的对象，下面的代码应该可以正常工作：

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

Answer 2

一个简单的解决办法是用 lookup[id(myobj)] = myotherobj 来代替 lookup[myobj] = myotherobj。对此方法有什么看法吗？

Answer 3

用可变对象作为键的映射通常比较麻烦。你真的想这样做吗？如果你认为你的对象是不可变的（在Python中其实没有办法完全保证不可变），或者你知道在用作映射的键时它们不会被改变，你可以用几种方法为它们实现自己的哈希函数。例如，如果你的对象只有可哈希的数据成员，你可以返回一个包含所有数据成员的元组的哈希值作为这个对象的哈希值。

如果你的对象像字典一样，你可以使用所有键值对的frozenset的哈希值。

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

这只有在所有值都是可哈希的情况下才有效。为了避免每次查找时都重新计算哈希值，你可以缓存哈希值，只有在某个“脏标志”被设置时才重新计算。