电话簿的数据结构，它可以按姓名搜索号码，也可以按号码搜索姓名 [英] A data structure for a phone book such that it can search a number by name and also search a name by number

问题描述

你知道以下面试问题的解决方案吗?

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.

<小时>

详情:

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

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?

推荐答案

这种数据结构被称为多索引容器.它们在大多数编程语言中并不常见，因为接口可能会变得非常复杂.Java、C# 和 - 最突出的 - 带有 Boost 库的 C++，请参阅 Boost.MultiIndex 文档，特别是 示例 4 关于双向地图:

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:

双向映射是 (const FromType,const ToType) 对的容器，因此没有两个元素具有相同的第一个或第二个组件(std::map只保证第一个组件的唯一性).快速查找是为两个键提供.该程序具有很小的西班牙语-英语在线查询两种语言单词的字典.

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屋！