use*_*288 7 hash dictionary hashmap data-structures
你知道以下面试问题的解决方案吗？
设计电话簿的数据结构,可以安全有效地按名称搜索数字,并按编号搜索名称.
细节:
stackoverflow上的解决方案都是关于哈希表的,但是,我必须为它构建2个哈希表,这需要两倍的空间.
如何以时间和空间效率,类型安全的方式只使用一个数据结构？
nos*_*sid 16
这种数据结构称为多索引容器.它们在大多数编程语言中并不常见,因为界面可能变得非常复杂.有实现在的Java,C#和-最显着的- C++与Boost库,看到Boost.MultiIndex的文档,特别是例如4对双向映射:
双向映射是(const FromType,const ToType)对的容器,因此不存在具有相同第一或第二组件的两个元素(std :: map仅保证第一个组件的唯一性).为两个密钥提供快速查找.该程序包含一个很小的西班牙语 - 英语词典,可以在线查询两种语言的单词.
多索引容器的基本思想是许多容器将它们的元素存储在包含指向其他节点的指针/引用的节点中(例如双链表).节点包含多个索引结构的链接,而不是仅存储单个容器的指针/引用.这至少适用于链表,排序树和唯一哈希索引.并且实现非常有效,因为每个元素只需要一个内存分配.