python中1:1映射的数据结构？

Question

我有一个问题，需要一个可逆的键到值的1:1映射。

这意味着有时我想找到给定值的键，但有时我想找到给定值的键。键和值都保证是唯一的。

x = D[y]
y == D.inverse[x]

最明显的解决方案是每次需要反向查找时都简单地反转字典：反转字典非常简单，there's a recipe here but for a large dictionary it can be very slow。

另一种选择是创建一个新的类，它将两个字典联合起来，每种查找一个字典。这很可能会很快，但占用的内存是单个dict的两倍

那么有没有更好的结构我可以使用？

• 我的应用程序要求这应该非常快，使用尽可能少的内存。
• 结构必须是可变的，并且强烈希望对象的变异不应导致它变慢（例如，强制一个完整的重新索引）
• 我们可以保证键或值（或两者）都是整数
• 这个结构很可能需要储存数千件甚至数百万件物品。
• 密钥和值保证是唯一的，即len（set（x））==len（x）for x in[D.Keys（），D.values（）]

Answer 1

The other alternative is to make a new class which unites two dictionaries, one for each > kind of lookup. That would most likely use up twice as much memory as a single dict.

不完全是这样，因为它们只会保存对同一数据的两个引用。在我看来，这不是一个糟糕的解决方案。

你考虑过内存中的数据库查找吗？我不确定它在速度上如何比较，但是在关系数据库中查找可以非常快。

Answer 2

class TwoWay:
    def __init__(self):
       self.d = {}
    def add(self, k, v):
       self.d[k] = v
       self.d[v] = k
    def remove(self, k):
       self.d.pop(self.d.pop(k))
    def get(self, k):
       return self.d[k]

Answer 3

The other alternative is to make a new class which unites two dictionaries, one for each kind of lookup. That would most likely be fast but would use up twice as much memory as a single dict.

不是真的。你量过了吗？由于两个词典都将对相同对象的引用用作键和值，因此所用的内存将只是词典结构。这比两次要少得多，而且无论数据大小如何，它都是固定的弹药。

我的意思是实际数据不会被复制。所以你不会花多少额外的记忆。

示例：

a = "some really really big text spending a lot of memory"

number_to_text = {1: a}
text_to_number = {a: 1}

只有一个“真的很大”字符串的副本存在，所以你最终只需要多花一点内存。一般来说是可以负担得起的。

我无法想象一个解决方案，如果您不花费至少足够的内存来存储反向查找哈希表（这正是您的“unite twodict解决方案中所做的），那么在按值查找时，您将拥有密钥查找速度。