哈希表中的部分搜索

Question

我需要创建一个电话簿。它包含姓名和号码。现在当我输入匹配的字母时应返回列表。例如，给定下面的例子，当我输入H时，应返回一个包含Harmer、Harris、Hawken、Hosler的列表。当我输入Ha时，应返回仅包含Harmer、Harris、Hawken的列表。

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

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

有什么想法如何实现它？ 提前致谢。

- Partha

---

你确定在这种情况下使用 HashMap 是个好主意吗？我认为其他数据结构可能更适合。 - Tikhon Jelvis

你是只想要第一个字母，还是在你输入时就将列表排除？例如，“Ha”的输入是否会将“Hosler”排除？ - Nate Zaugg

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）。

- Paŭlo Ebermann

---

@Paŭlo Ebermann：为什么使用 Trie 树，它又是如何节省空间的呢？{https://dev59.com/cWsy5IYBdhLWcg3w3Rzc}？ - Rajat Gupta

你也可以使用前缀 + "\uffff" 作为结束符。 - Tires

@PaŭloEbermann 我有同样的情况。但现有的映射是HashMap实现（用于10k+元素），不能更改。现在，为了按照上述解决方案实现这一点，如果我选择将Hashmap中包含的整个内容转储到TreeMap中，那么TreeMap本身的构建将非常昂贵（因为它构建了一个排序结构），其余部分可能很容易和快速。对于如何满足我的要求，您有什么建议吗？ - abksrv

@abksrv 如果这只是一次搜索，那么在HashMap的所有条目上进行单次迭代应该是最快的。如果您想要更频繁地执行此操作，请将数据转移到更好的结构中。（另外，测量一下：也许对于您的数据集和硬件来说，甚至不需要优化。） - Paŭlo Ebermann

Answer 2

这需要使用Trie数据结构。请查看这个问题以获取Java实现。我使用了这个。

- Bozho

---

谢谢Bozho，你的链接很有用！但是自那个问题被回答以来已经过去了将近3年。现在是否有更好的解决方案，你是否知道？ - Rajat Gupta

链接又坏了，Bozho。 - mcvkr

Answer 3

删除所有不包含关键部分的值：

yourMap.keySet().removeIf(key -> !key.contains(keyPart));

Or regex:

yourMap.keySet().removeIf(key -> !key.matches(".*keyPart.*"));

或者对流进行过滤并收集到一个新的map中：

最初的回答：

yourMap.entrySet().stream().filter(e -> e.getKey().contains(keyPart)).collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue()));

- Justinas Jakavonis

Answer 4

将所有内容放入MultiMap中（或者只需将List作为HashMap的值存储）。对于“Brown”，请存储：

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

如果您稍后添加了“Bradley”：

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

然后再有另一个映射将“Brown”或“Bradley”映射到电话号码。

- dgrant

---

从这个数据结构中添加和删除东西将会非常昂贵。 - Mark Elliot

我同意。但我们甚至不知道他的“电话簿那种东西”有多大。我更愿意先做一些简单的事情，然后再进行优化。这似乎是最简单的事情。 - dgrant

访问将是O(1)，而对于树来说，它将是log(n)。如果你正在做自动完成之类的事情，这不是更重要的吗？数据集更新的频率有多高？如果获取操作比设置操作频繁得多，那么添加/删除的速度慢又有什么关系呢？在这里添加和删除甚至并不那么糟糕，我认为。 - dgrant

Answer 5

使用guava Multimap可以轻松解决问题。

关键是名字的第一个字母，值是一个Collection，其中包含所有以该键（第一个字母）开头的姓名-电话对。

例如：

    public void test(){
      //firstLetter -> list of name-phone pair
      Multimap<String, Pair> 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<String, Pair> 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+"]";
      }

}

- 卢声远 Shengyuan Lu