java - 一句话检查HashMap中的key是否存在

Question

我有一个 HashMap 存储 <city, state> 对，其中城市是键，状态是值。现在城市名称可能是多个单词，例如“新德里”。现在有很多句子可能包含也可能不包含城市名称。我想为他们每个人检查一下。

一种方法是继续扫描 HashMap 并检查每个键是否存在于句子中。但是，如果 HashMap 包含数百万个条目，那将是一种非常低效的方法。

所以我正在寻找是否有任何有效的方法来做同样的事情。谢谢你。

Answer 1

1、将句子拆分为单词，将城市名称拆分为单词，您可以通过哈希检查它们。

2、算法思路：

AC FSM，你可以用一个句子匹配多个字符串，只需一次。

后缀树，还有一个算法。

我认为两者相似。您可以选择一个。

Answer 2

尝试

    TreeMap<String, String> map = new TreeMap<>();
    map.put("Delhi", "State");
    map.put("New Delhi", "State");
    map.put("New York", "State");
    String[] a = map.keySet().toArray(new String[0]);
    Set<String> found = new HashSet<>();

    Scanner s = new Scanner("First is Delhi, next is New Delhi");
    s.useDelimiter("[ .,\n\t\r]");
    String prev = "";    // previous word
    while (s.hasNext()) {
        String n = s.next();
        if (!prev.isEmpty()) {
            n = prev + n;
        }
        int i = Arrays.binarySearch(a, n);
        if (i >= 0) {
            found.add(n);
            prev = "";
        } else {
            i = -i - 1;
            if (i < a.length && a[i].startsWith(n)) {
                prev = n + " ";
            } else {
                prev = "";
            }
        }
    }
    System.out.println(found);

输出

[New Delhi, Delhi]

也许它有一些错误，但想法是使用排序的字符串数组（城市）和 Arrays.binarySearch 快速找到插入位置并检查元素（城市）是否以当前单词开头。