电话簿的数据结构，可以按名称搜索号码，也可以按号码搜索名称 [英] A data structure for a phone book such that it can search a number by name and also search a name by number
问题描述
设计电话簿的数据结构，可安全地使用
有效地按名称搜索一个号码，并通过号码搜索一个名称。
详细信息：
在stackoverflow上找到的解决方案都是关于哈希表的，但是，我必须为此创建2个哈希表，这需要两倍的空间。
如何以时间和空间高效的，类型安全的方式仅使用一个数据结构来完成它？
这种数据结构称为多索引容器。它们在大多数编程语言中并不常见，因为接口可能非常复杂。
在 Java ， C＃和 - 最显着的 - C ++与Boost库，请参阅Boost.MultiIndex文档，特别是 example 4 关于双向映射：
双向映射是（const FromType，const ToType）对的容器，使得不存在具有相同第一或第二组件的
两个元素（std :: map
仅保证第一个组件的唯一性）。快速查找是为两个密钥提供的
。该程序提供了一个小小的西班牙文 - 英文
字典，可在线查询两种语言的文字。 basic多索引容器的想法是许多容器将其元素存储在包含指向其他节点的指针/引用（例如双链表）的节点中。不是只存储单个容器的指针/引用，而是包含多个索引结构的链接。这至少适用于链接列表，排序树和唯一散列索引。实现非常高效，因为每个元素只需要一次内存分配。Do you know a solution to the following interview 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.
Details:
The solutions found on stackoverflow are all about hashtables, but, I'd have to build 2 hashtables for that, which requires twice the space.
How to do it with only one data structure in a time- and space-efficient, type-safe manner?
解决方案Such data structures are known as multi-index containers. They are not very common in most programming languages, because the interface can get quite complex. There are implementations in Java, C# and - most prominently - C++ with the Boost library, see Boost.MultiIndex Documentation, in particular example 4 about bidirectional maps:
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.
The basic idea of multi-index containers is that a lot of containers store their elements in nodes that contain pointers/references to other nodes (e.g. double linked lists). Instead of only storing the pointers/references for a single container, a node contains the links for several index structures. This works at least with linked lists, sorted trees and unique hash indices. And the implementation is very efficient, because only one memory allocation is required per element.
这篇关于电话簿的数据结构，可以按名称搜索号码，也可以按号码搜索名称的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
