设计一个电话簿数据结构,用于存储姓名和电话号码,以便我们可以根据给定的姓名搜索键和反过来搜索电话号码。我们可以使用两个哈希映射来实现:
但这需要两倍的内存。有人能推荐其他解决方案吗?
Map<String,int>
Map<int,String>
但这需要两倍的内存。有人能推荐其他解决方案吗?
Map<String,int>
Map<int,String>
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]
Map<String,List<String>>
,或者只使用字符串指针(用 C++ 的术语来说),以避免冗余: Map<String*,List<String*>>
。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.
使用二叉搜索树来实现电话簿是最好的方法。想一想移动电话联系人列表的实际实现方式,它是按字母顺序排序的。如果使用映射模板,我们将无法获得排序后的列表。您无法对映射的元素进行排序,这也不是有效的方法。
唯一的方法是使用二叉树。因为在添加新条目时,它会以有序的方式插入。因此,不需要再进行排序。它已经被排序了。请记住,在二叉树中,左子树小于根节点,根节点小于右子树。