java - 像 startsWith() 不是 equals() 这样的快速字符串搜索

Question

我有一个有序列表(字典 - 100K 个单词)和许多要经常在此列表上搜索的单词。所以性能是个问题。我知道 HashSet.contains(theWord) 或 Collections.binarySearch(sortedList, theWord) 非常快。但我实际上并不是在寻找整个词。

我想要的是假设搜索“se”并获取所有以“se”开头的单词。那么在 Java 或任何库中是否有现成的解决方案？

一个更好的例子:在一个排序列表上，一个快速解决以下操作的方法

List.subList(String beginIndex, String endIndex)//返回区间

myWordList.subList(“ab”, “bc”);

注意:这是一个非常相似的问题，但接受的答案并不令人满意。 Overriding HashSet's Contains Method

Answer 1

您在这里寻找的是一种通常称为“trie”的数据结构:

http://en.wikipedia.org/wiki/Trie

它将字符串存储在由前缀索引的树中，其中树的第一层包含字符串的第一个字符，第二层包含第二个字符，等等。结果是它允许您提取非常大的子集极快地按前缀设置字符串。