Python中的可哈希灵活标识符

Question

我正在尝试在Python中创建一种可哈希的标识符，用来识别图中的节点。问题是，有些节点的属性不同。如果这些节点的属性用字典来表示，字典的内容是属性和对应值的关系：

idA = {'type':'A', 'name':'a_100'}
idB = {'type':'B', 'name':'b_3', 'value':7}

我希望__hash__()和__eq__()能使用这样的元组对((key1,value1), (key2,value2), ...)。

字典是最理想的选择，因为我需要频繁检查这些属性，而字典查找的效率应该很高（我会使用很多标识符，每个标识符会有很多属性）。但是，字典本身是不可哈希的。

如果用元组对构成一个不可变集合（frozenset），这样就能正确哈希，但查找效率会高吗？

如果我声明一个空类，然后为它设置属性，这样可以实现我想要的效果（可能在内部使用字典），但我不知道怎么给它哈希。也许可以用inspect或dir()来哈希它的成员值？

class identifier():
    pass
idA = identifier()
idA.type = 'A'
idA.name = 'a_100'

如果有办法基于属性和值的元组对来使用哈希（和==运算符），那也能实现我想要的效果。

或者有没有什么变通方法，可以创建一个等价的数据类型，满足这种类比：frozenset 对应 set，那么 ? 对应 dict。

谢谢你的帮助。

---

编辑：

这样做方向对吗？

class identifier(dict):
    def to_frozenset(self):
        return frozenset([(k,self[k]) for k in self])
    def __hash__(self):
        return hash(self.to_frozenset())
    def __eq__(self, rhs):
        return self.to_frozenset() == rhs.to_frozenset()
    def __ne__(self, rhs):
        return not self == rhs

这样做会改变计算复杂度，使得查找标识符属性很快，但哈希标识符或检查两个标识符是否相等会很慢。如果有办法缓存它的哈希值（并且在哈希值缓存后不允许字典改变），而且我们能保证标识符类型的哈希冲突很少（这样检查相等的情况就会很少），那也许这是个好解决方案？告诉我你的想法！

Answer 1

我不确定这能否解决你的问题，但如果你想让一个对象可以被哈希（也就是可以用来做字典的键），你可以这样实现：

class Hashable(object):
    def __hash__(self):
        return hash((self.__class__.__name__,
                     tuple(self.__dict__.items())))

这样你就能以一种结构化的元组格式获取对象的数据，同时还会有类名作为某种哈希签名。你甚至可以扩展 dict 来在这个类中使用。

Answer 2

其实没有叫做 frozendict 的东西。不过，collections.namedtuple 是一种类似的东西，可能会对你有帮助。

Answer 3

不要直接从字典（dict）继承，而是把它封装起来。这样可以确保它不会被意外修改。

关于缓存，你可以记住一个不可变集合（to_frozenset）或者它的哈希值。根据使用的方式，可以记住哈希值，这样在进行哈希和不相等比较时会很快，如果哈希值匹配，再去比较不可变集合。

不过，你现在对性能的担忧有点过了，毕竟你还没有做过性能测试。先实现一个最简单的版本。如果这个版本运行得快，那就可以了。如果不快，再进行性能测试，然后找出逐步改进的办法。