在HashMap中进行部分搜索

我需要创建电话簿类的东西。 它包含姓名和号码。 现在当我输入字母时，应该返回匹配列表。 对于下面给出的示例，当我键入H时，应返回包含Harmer，Harris，Hawken，Hosler的列表。 当输入Ha然后列出只包含Harmer，Harris，Hawken的列表应该返回。

Map nameNum = new HashMap(); nameNum.put("Brown", "[phone]"); nameNum.put("Bob", "[phone]"); nameNum.put("Harmer", "[phone]"); nameNum.put("Harris", "[phone]"); nameNum.put("Hawken", "[phone]"); nameNum.put("Hosler", "[phone]"); 

知道如何实现它？ 提前致谢。

Answer 1

是的，HashMap不是正确的数据结构。 正如Bozho所说， Trie将是正确的。

使用Java的板载工具，可以使用TreeMap（或任何实际的SortedMap ）：

 public  SortedMap filterPrefix(SortedMap baseMap, String prefix) { if(prefix.length() > 0) { char nextLetter = prefix.charAt(prefix.length() -1) + 1; String end = prefix.substring(0, prefix.length()-1) + nextLetter; return baseMap.subMap(prefix, end); } return baseMap; } 

输出甚至可以按键排序。

这是一个用法示例：

 SortedMap nameNum = new TreeMap(); // put your phone numbers String prefix = ...; for(Map.Entry entry : filterPrefix(nameNum, prefix).entrySet()) { System.out.println(entry); } 

如果您希望前缀filter不依赖于大小写差异，请为您的地图使用合适的比较器（如具有合适强度设置的Collator或String.CASE_INSENSITIVE_ORDER ）。

Answer 2

这需要Trie数据结构。 对于java实现，请参阅此问题 。 我用过这个 。

Answer 3

将它全部放在MultiMap中（或者只将List存储为HashMap中的值）。 对于“布朗”，商店：

 "B"->["Brown"] "BR"->["Brown"] "BRO"->["Brown"] 

如果你以后添加“Bradley”：

 "B"->["Brown", "Bradley"] "BR"->["Brown", "Bradley"] "BRO"->["Brown"] "BRA"->["Bradley"] 

等等…

然后有另一张地图将“布朗”或“布拉德利”映射到电话号码。

Answer 4

使用番石榴Multimap将简化您的解决方案。

密钥是名字的第一个字母，值是包含所有名称 – 电话对的Collection ，其名称以密钥（第一个字母）开头。

例：

  public void test(){ //firstLetter -> list of name-phone pair Multimap mMap = ArrayListMultimap.create(); put(mMap, "Brown", "[phone]"); put(mMap, "Bob", "[phone]"); put(mMap, "Harmer", "[phone]"); put(mMap, "Harris", "[phone]"); put(mMap, "Hawken", "[phone]"); put(mMap, "Hosler", "[phone]"); //Test System.out.println(mMap.get("H")); } void put(Multimap mMap, String name, String phone){ mMap.put(name.substring(0,1), new Pair(name, phone)); } public static class Pair{ String name; String phone; public Pair(String name, String phone) { this.name = name; this.phone = phone; } @Override public String toString() { return "Pair [name="+name+", phone="+phone+"]"; } 

}