双向地图的替代实现的空间开销是多少，理想情况下不需要将数据集大小加倍？
Stack Overflow 上有很多关于双向映射实现的问题，其中许多询问的是效率。然而，虽然他们有关于如何实现双向地图的答案，但我还没有看到任何一个真正解决这些问题的效率部分。
考虑到这一点，我明确不询问如何实现一个简单的双向地图（正如其他答案所涵盖的那样，使用 2 个单向地图就足够了）。
我还没有完全解决的一个想法是，使用一组前缀树可能会获得相同的结果，从而通过键和值中的公共前缀节省一些空间，但我不确定这会好得多，而且我确信有人在某处对此类方法进行了一些分析，我只是无法找到参考资料。最重要的是，这符合“仅混搭 2 张地图”的形式主义，所以我很惊讶无法找到更奇特的替代方案。
当我问这个问题时，我没有意识到这一点，但是有一种简单的（如果可怕的话）方法可以存储双向映射，而根本不需要复制键或值。
考虑任意实现的地图；让我们以哈希表为例。由于检索时间约为 O(1)，我们可以做出一个非常可怕的权衡，我们可以迭代一个哈希表并将其反转，而不是存储两个哈希表，这应该需要 ~O(N) 时间。该反转应该只需恒定的内存开销即可完成，并且在完成反转后可以丢弃该内存。当然，不同的地图实现，复杂度会有很大不同。
唯一可能有用的情况是您可以接受批量 get() 的情况。您将花费一些时间立即解决 get(key) 查询，并对一堆 get(value) 调用进行排队，反转映射，解决所有排队的调用，并将 get(key) 调用排队，直到下一次翻转。
虽然这确实回答了我的问题：是否可以有一个不重复数据的双向地图，但在任何情况下它都不是一个非常有用的解决方案，所以我将保留这个问题以查看是否存在其他解决方案以及哪种解决方案他们表现出的权衡。