在HashMap中进行部分搜索

Question

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

  Map<String, String> nameNum = new HashMap<String, String>();

  nameNum.put("Brown", "+1236389023");
  nameNum.put("Bob", "+1236389023");
  nameNum.put("Harmer", "+1236389023");
  nameNum.put("Harris", "+1236389023");
  nameNum.put("Hawken", "+1236389023");
  nameNum.put("Hosler", "+1236389023");

任何想法如何实现呢？提前致谢.

Answer 1

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

使用Java的板载工具,可以使用TreeMap(或任何SortedMap):

public <V> SortedMap<String, V> filterPrefix(SortedMap<String,V> 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<String, String> nameNum = new TreeMap<String, String>();
// put your phone numbers

String prefix = ...;
for(Map.Entry<String,String> entry : filterPrefix(nameNum, prefix).entrySet()) {
    System.out.println(entry);
}

如果您希望前缀过滤器不依赖于大小写差异,请为您的地图使用合适的比较器(例如Collator,具有合适的强度设置,或String.CASE_INSENSITIVE_ORDER).

Answer 2

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