data-structures - 电话簿的数据结构，它可以按姓名搜索号码，也可以按号码搜索姓名

Question

您知道以下面试问题的解决方案吗？

Design a data structure for a phone book that can safely and efficiently search a number by name and also search a name by number.

细节:

在 stackoverflow 上找到的解决方案都是关于哈希表的，但是，我必须为此构建 2 个哈希表，这需要两倍的空间。

如何以一种节省时间和空间、类型安全的方式只使用一种数据结构来做到这一点？

Answer 1

这种数据结构被称为 多索引容器 .它们在大多数编程语言中并不常见，因为界面会变得非常复杂。
在 Java 中有实现, C#以及 - 最突出的 - 带有 Boost 库的 C++，参见 Boost.MultiIndex Documentation ，特别是example 4关于 双向映射 :

A bidirectional map is a container of (const FromType,const ToType) pairs such that no two elements exists with the same first or second component (std::map only guarantees uniqueness of the first component). Fast lookup is provided for both keys. The program features a tiny Spanish-English dictionary with online query of words in both languages.

多索引容器的基本思想是许多容器将它们的元素存储在包含指向其他节点的指针/引用的节点中(例如双链表)。一个节点不仅存储单个容器的指针/引用，还包含多个索引结构的链接。这至少适用于链表、排序树和唯一哈希索引。并且实现非常高效，因为每个元素只需要分配一次内存。