python - 1 :1 mappings in python? 的数据结构

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 的内存。

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

• 我的应用程序要求它应该非常快并且使用尽可能少的内存。
• 结构必须是可变的，并且强烈希望改变对象不应该导致它变慢(例如强制完全重新索引)
• 我们可以保证键或值(或两者)都是整数
• 很可能需要该结构来存储数千甚至数百万个项目。
• Keys & Valus 保证是唯一的，即 len(set(x)) == len(x) for for x in [D.keys(), D.valueies()]

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 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}

只存在一个“非常大”字符串的副本，因此您最终只花费了更多的内存。这通常是负担得起的。

如果您没有花费至少足够的内存来存储反向查找哈希表(其中正是您的“联合两个 dicts”解决方案中正在做的事情)。