在哈希图中进行部分搜索

filtering java map

2022-09-01 06:54:12

我需要创建电话簿之类的东西。它包含名称和编号。现在，当我键入字母时，应返回匹配列表。对于下面给出的示例，当我键入 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");

任何想法如何实现它？提前致谢。

答案 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);
}

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

答案 2

这需要一个Trie数据结构。有关 Java 实现，请参阅此问题。我用了这个。