Python中的可逆字典
我想在Python中存储一些数据，形式类似于字典：{1:'a', 2:'b'}。每个值都是独一无二的，不仅在其他值中独特，在键中也是如此。
有没有简单的数据结构可以让我无论是用“键”还是“值”都能找到对应的对象？比如：
>>> a = {1:'a', 2:'b'}
>>> a[1]
'a'
>>> a['b']
2
>>> a[3]
KeyError
这些“键”是标准的Python整数，而“值”是短字符串（小于256个字符）。
我现在的解决方案是创建一个反向字典，如果在原始字典中找不到结果，就去搜索这个反向字典：
pointsreversed = dict((v, k) for k, v in points.iteritems())
def lookup(key):
return points.get(key) or pointsreversed.key()
这样做会占用两倍的空间，这并不好（我的字典可以大到几百兆），而且平均速度慢了50%。
补充说明：正如一些回答中提到的，两个字典并不会使内存使用量翻倍，因为只是字典本身在重复，而不是其中的项。
有没有更好的解决方案呢？
7 个回答
在《计算机程序设计艺术》第三卷中，Knuth提到了一些关于次要键查找的内容。对于你的问题来说，值可以被视为次要键。
第一个建议就是你已经做的：根据值建立一个高效的键索引。
第二个建议是建立一个大型的B树，这是一种复合索引，包含了聚集数据的结构，其中的分支节点包含值，而叶子节点则包含键数据和指向更大记录的指针（如果有的话）。
如果你的数据是几何形状的（看起来是这样），那么有一种叫做邮局树的结构。它可以回答类似“离点x最近的物体是什么”的问题。这里有一些例子：http://simsearch.yury.name/russir/01nncourse-hand.pdf。对于这种查询，另一个简单的选择是四叉树和k-d树。http://en.wikipedia.org/wiki/Quadtree
最后一个选择是组合哈希，这种方法将键和值结合成一种特殊的哈希，可以让你在没有两个值的情况下也能高效查找。我在网上找不到好的组合哈希解释，但在《计算机程序设计艺术》第三卷第二版的573页上有相关内容。
当然，对于其中一些方法，你可能需要自己编写代码。不过，如果内存或性能真的很重要，你可能值得花时间去实现这些。
如果你的键和值没有重叠，一个简单的方法就是把它们放在同一个字典里。比如：
class BidirectionalDict(dict):
def __setitem__(self, key, val):
dict.__setitem__(self, key, val)
dict.__setitem__(self, val, key)
def __delitem__(self, key):
dict.__delitem__(self, self[key])
dict.__delitem__(self, key)
d = BidirectionalDict()
d['foo'] = 4
print d[4] # Prints 'foo'
（你可能还想实现一些方法，比如 __init__、update 和 iter*，这样它就能像真正的字典一样工作，具体取决于你需要多少功能。）
这样做只需要查找一次，虽然在内存上可能不会节省太多（毕竟字典的条目数量还是翻倍了）。不过要注意，这种方法和你原来的方法都不会占用两倍的空间：字典只占用指向对象的引用的空间（实际上就是指针），再加上一些额外的开销。你的数据本身占用的空间不会重复计算，因为它们指向的是同样的对象。