内射双向映射

Question

我经常处理 injective 的映射。在编程术语中，这可以表示为字典，其中所有值都是唯一的，当然还有所有键。

是否有内存高效的单射映射数据结构，具有您期望从字典中获得的所有时间复杂度属性？

例如：

d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'}

d.get(2) = 'b'  # this works with a normal dictionary
d.get('b', reverse=True) = 2  # but this is not possible

Two way/reverse map中的所有解决方案似乎都需要使用或组合两组映射，重点是使双向映射的操作更容易。这对于完全适合内存的小型词典来说很好，但对于大型词典就不好了。

与仅存储单向映射的常规字典相比，存储单射双向映射不应有额外的内存开销。

我知道字典使用散列 table，它使用关联数组数据类型。根据定义，关联数组使用唯一键实现键 -> 值映射。是否有可能在理论上或实践中产生允许反向查找的智能单射映射？

如果不可能，我希望能解释一下为什么这样的构造很难或不可能以与字典相同的效率来实现。

更新

在与@rpy 的讨论之后（请参阅下面的评论），关于如何使用完美的可逆哈希函数设置 python 类似字典的对象的任何信息都会很有用。但是，当然，一个可行的实现将是理想的（我已经尝试过perfection）。

Answer 1

您问题的最终答案是：否（对于任何有效的实施）

您提出了两个不能同时满足的要求：

不要为反向映射使用额外的内存
不要为进行（反向）查找添加额外的时间

为什么这两个限制禁止解决方案？

映射是值对（元组）。最简单的实现是：

顺序搜索所有元组以进行匹配。

前向和后向映射的复杂度相同。
然而，这显然违背了time-complexity properties you expect from dictionaries的预期：

如果您允许 O(n) 的复杂性，那么按顺序搜索元组集将为您提供合适的解决方案。

通常字典实现会尝试降低到 O(1) 或至少 O(n*log(n)) 复杂度.这是通过引入额外的数据来加速查找来实现的，例如哈希或树。不幸的是，此类辅助工具只能在一个方向上提供帮助，因为它们要么处理键（正向映射情况），要么处理值（反向映射情况）。

因此，一旦您需要降低查找的复杂性（这也适用于修改复杂性，但通常字典是为快速查找量身定制的），您将需要添加数据以实现速度。

整个问题归结为经典内存与速度权衡。

编辑：

在一般实现中解决该问题的方法（对于键和值允许获得数字表示的情况，如果它们首先不是整数）可能是：

为key计算一个哈希值，为value计算一个哈希值，并在两个哈希值下注册元组。这样你就可以获取键或值并识别匹配的元组和 return 正确的结果。当您允许 returning 组匹配元组时，这甚至适用于非单射情况。

这将需要更多 space（哈希条目加倍），同时将查找复杂度保持在基于哈希的字典的典型值范围内。您可能需要注意哈希桶的大小（冲突链的长度），尤其是当键和值的值集不相交时）

内射双向映射

Injective two-way mappings

python

hash

dictionary

perfect-hash

injective-function