我有一个有序列表(字典 - 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
最佳答案
您在这里寻找的是一种通常称为“trie”的数据结构:
http://en.wikipedia.org/wiki/Trie
它将字符串存储在由前缀索引的树中,其中树的第一层包含字符串的第一个字符,第二层包含第二个字符,等等。结果是它允许您提取非常大的子集极快地按前缀设置字符串。
关于java - 像 startsWith() 不是 equals() 这样的快速字符串搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3354882/