在字符串集合中查找以特定字符开头的字符串的最快方法

Question

我有一大批字符串，我想要查找以"Foo"开头或以"Bar"结尾的字符串。为了获得最快的结果，最好使用哪种集合类型？（我正在使用Java）

我知道HashSet对于完全匹配非常快，但对于部分匹配可能不是最优解。那么，除了遍历List之外，我应该使用LinkedList或类似类型吗？是否有针对此类查询进行优化的集合类型？

- Peterdk

---

你应该使用 trie 数据结构，Guava 库中有一些实现。 - nachokk

Answer 1

这个问题最好的集合类型是SortedSet。实际上，你需要两个：

1. 按照正常顺序排列的单词。
2. 将字符倒置后排列的单词。

一旦创建了这些SortedSet，你可以使用方法subSet来查找你想要的内容。例如：

1. Words starting with "Foo":

    forwardSortedSet.subSet("Foo","Fop");
   

2. Words ending with "Bar":

    backwardSortedSet.subSet("raB","raC");
   

我们之所以要“加”1到最后一个搜索字符，是为了获得整个范围。 “结束”单词被排除在subSet之外，因此没有问题。

编辑：在标准Java库中实现SortedSet的两个具体类中，使用TreeSet。另一个（ConcurrentSkipListSet）面向并发程序，因此不针对此情况进行优化。

- Mario Rossi

---

为什么使用集合而不是排序列表？ - Kon

你需要倒置集合用于什么？用于查找以特定字符结尾的字符串吗？ - Peterdk

@Kon：因为它不存在。https://dev59.com/c2oy5IYBdhLWcg3wKrCs - Amadan

是的，可以。您可以反转搜索词，然后在反向集合中搜索起始字符。例如，要在字符串末尾搜索“Bar”，您需要反转所有字符串，然后搜索以“raB”开头的字符串。这样可以继续使用二进制搜索，并将搜索时间保持在log n复杂度下。 - Kon

@Amadan 一个List可以很容易地进行排序，而且OP从未指定允许唯一性。 - Kon

Answer 2

这已经有一段时间了，但我现在需要实现它并进行了一些测试。

我已经有一个HashSet<String>作为源，因此所有其他数据结构的生成都包括在搜索时间内。使用了100个不同的源，每次需要重新生成数据结构。每次只需要匹配一些单个字符串。这些测试在Android上运行。

方法：

1. 通过HashSet进行简单循环，并对每个字符串调用endsWith()

2. 通过HashSet进行简单循环，并在每个字符串上执行预编译的Pattern匹配（正则表达式）。

3. 将HashSet转换为由\n连接的单个String，然后在整个字符串上进行单个匹配。

4. 生成反向Strings的SortedTree，然后使用subset()进行匹配，如@Mario Rossi所解释的那样。

结果：

Duration for method 1: 173ms (data setup:0ms search:173ms)
Duration for method 2: 6909ms (data setup:0ms search:6909ms)
Duration for method 3: 3026ms (data setup:2377ms search:649ms)
Duration for method 4: 2111ms (data setup:2101ms search:10ms)

结论： SortedSet/SortedTree 在搜索方面非常快，比循环遍历所有 Strings 的速度要快得多。但是，创建这种数据结构需要很长时间。在 Android/Java 上，正则表达式的速度要慢得多，但是将数百个 Strings 生成一个单独的大的 String 更成为瓶颈。

如果只需要进行少量匹配，则最好循环遍历集合。如果您需要进行更多的匹配，则使用 SortedTree 非常有用！

- Peterdk

Answer 3

如果单词列表是稳定的（添加或删除的单词不多），第二个很好的选择是创建两个列表：

1. 一个按正常顺序排列的单词列表。
2. 第二个是每个单词中字符反转的列表。

为了提高速度，将它们制作为ArrayList。 不要使用LinkedList或其他在随机访问时性能极差的变体（这是二进制搜索的核心；请参见下文）。

列表创建后，可以使用方法Collections.sort（仅一次）进行排序，然后使用Collections.binarySearch进行搜索。 例如：

    Collections.sort(forwardList);
    Collections.sort(backwardList);

然后要搜索以“Foo”开头的单词：

    int i= Collections.binarySearch(forwardList,"Foo") ;
    while( i < forwardList.size() && forwardList.get(i).startsWith("Foo") ) {
        // Process String forwardList.get(i)
        i++;
    }

以"Bar"结尾的单词：

    int i= Collections.binarySearch(backwardList,"raB") ;
    while( i < backwardList.size() &&  backwardList.get(i).startsWith("raB") ) {
        // Process String backwardList.get(i)
        i++;
    }

- Mario Rossi