设计一个电话簿的数据结构

Question

设计一个电话簿数据结构，用于存储姓名和电话号码，以便我们可以根据给定的姓名搜索键和反过来搜索电话号码。我们可以使用两个哈希映射来实现：

Map<String,int>
Map<int,String>

但这需要两倍的内存。有人能推荐其他解决方案吗？

- akshay

---

假设您的字符串长度大于2，使用map不会占用两倍内存，因为map只保存（或可以保存）对字符串的引用，而不是实际的字符串，因此您只需将字符串存储一次，并拥有两个指向它的指针，这并不太糟糕。 - amit

电话号码也应该是一个“字符串”。如果这是一项作业，则最好添加一个标签。 - Nick Dandoulakis

@NickDandoulakis 是的！电话号码不是数字！ - Nick Johnson

"twice"意味着“常数”（内存复杂度），对于您的需求（双重映射）来说并不算太糟糕。我无法为您推荐更好的（数据结构），而不会破坏运行时间！ - xerx593

Answer 1

一个双向映射（或“双向映射表”）是一种保留其值和键的唯一性的映射表。这个限制使得双向映射表能够支持“反向视图”，即另一个包含与此映射表相同条目但键和值颠倒的双向映射表。

http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/BiMap.html

BiMap<String, Integer> biMap = HashBiMap.create();

biMap.put("Mike", 123);
biMap.put("John", 456);
biMap.put("Steven", 789);

BiMap<Integer, String> invertedBiMap = biMap.inverse();

编辑：多重映射

Multimap<String, String> multimap = HashMultimap.create();
multimap.put("John", "111111111");
multimap.put("John", "222222222");
multimap.put("Mike", "333333333");

System.out.println(multimap.get("John")); //[222222222, 111111111]

for(Map.Entry<String, String> entry : multimap.entries()){
    if(entry.getValue().equals("222222222")){
        System.out.println(entry.getKey()); //John
    }
}
//or

Multimap<String, String> inverted = HashMultimap.create();
Multimaps.invertFrom(multimap, inverted);
System.out.println(inverted.get("222222222")); //[John]

- Infinity

Answer 2

一个人可以有多个号码，而一个号码也可以属于多个人（家庭成员）。正如尼克所说，电话号码在一般情况下可能会有非数字字符。考虑到这些因素，你可能会使用 Map<String,List<String>>，或者只使用字符串指针（用 C++ 的术语来说），以避免冗余： Map<String*,List<String*>>。

- Dialecticus

Answer 3

另一种可能性是将字符串存储在一棵trie中，并使用'$'符号表示每个字符串的结尾。对于每个步骤，使用双重链接指针，并从每个'$'（名称结尾）到其编号（在数组或列表中）保持双重链接指针。

现在，当你想从名字中获取电话时：

find the '$' indicating the end of the word for this string.
it is connected to a number in a list - that is your number.

当你想从电话中获取一个名字时：

find the number, it is connected to a '$' sign.
follow the up-links all the way to the root, this will get you the name (reversed). 
reverse it and you are done.

此外，正如我在评论中所说（关于双重映射方法）：假设您的字符串相当大，并且映射将保存指向字符串的指针/引用（而不是实际字符串），则可以假定所需的存储空间不会翻倍，而是更好的一些东西。

- amit

Answer 4

使用二叉搜索树来实现电话簿是最好的方法。想一想移动电话联系人列表的实际实现方式，它是按字母顺序排序的。如果使用映射模板，我们将无法获得排序后的列表。您无法对映射的元素进行排序，这也不是有效的方法。

唯一的方法是使用二叉树。因为在添加新条目时，它会以有序的方式插入。因此，不需要再进行排序。它已经被排序了。请记住，在二叉树中，左子树小于根节点，根节点小于右子树。

- KjD

---

映射被实现为红黑树（不是通过定义，而是通过约定）。也许你和unordered_map（又名哈希表）搞混了？ - sehe