-1

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

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

例如：

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中的所有解决方案似乎都需要使用或组合两组映射，重点是使在双向映射上执行操作更容易。这对于完全适合内存的小型词典来说很好，但对于大型词典来说却不是很好。

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

我了解字典使用哈希表，它使用关联数组数据类型。根据定义，关联数组使用唯一键实现键 -> 值映射。理论上或实际上是否有可能产生一个允许反向查找的智能单射映射？

如果不可能，我会很感激解释为什么这样的结构很难或不可能以与字典相同的效率实现。

更新

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

4

1 回答 1

1

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

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

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

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

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

顺序搜索所有元组以查找匹配项。

这对于前向和后向映射具有相同的复杂性。
但是，这显然违反了以下预期time-complexity properties you expect from dictionaries：

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

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

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

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

编辑：

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

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

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

于 2018-02-01T09:29:14.020 回答