Python：根据键从集合中获取项

Question

我有一个类，这个类里面有一个自定义的哈希方法。

class Test(object):

    def __init__(self, key, value):
        self.key = key # key is unique
        self.value = value

    def __hash__(self):
        # 'value' is unhashable, so return the hash of 'key'
        return hash(self.key)

我用这个类的对象创建了一个集合（set）。

t0, t1, t2 = Test(0, 10), Test(1, 5), Test(2, 10)
s = set([t0, t1, t2])

现在，我想知道有没有办法通过一个key来找到集合中的对象。也就是说，我想这样做：

find_using_key(s, 1) # should return [t1]

我知道可以通过遍历集合里的每个项目来实现这个，但我觉得应该有一种O(1)的方式来做到这一点，因为key实际上决定了在set中的“位置”。

Answer 1

如果你不需要使用集合，那你可以通过字典来实现 O(1) 的查找速度。只需要把你的键当作字典的键就可以了：

d = {}
d[t0.key] = t0
d[t1.key] = t1
d[t2.key] = t2

你还可以用字典推导式来让代码看起来更简洁：

d = {t.key: t for t in [t0,t1,t2]}

或者在 2.6 版本中：

d = dict((t.key,t) for t in [t0,t1,t2])

Answer 2

...因为键实际上决定了集合中的“位置”

这其实不太准确。两个元素如果有相同的key是可以同时存在于集合中的：

>>> t0, t1 = Test(1,1), Test(1,2)
>>> len(set((t0,t1)))
2

哈希值并不代表相等。因为可能会出现哈希冲突，所以这也是不可能的。

关于你的问题：不要使用set。它是通过一个抽象接口定义的，主要有插入和查找这两个操作。它并没有提供你想要的操作。至于底层的实现是否理论上能支持你想要的操作，这并不重要。相反，使用dict，将键和实例关联起来。