如何在Java中创建简单的前缀索引？

Question

我有大量的网址,我想实现自动完成.我不喜欢天真方法的复杂性,因为它与设定大小呈线性关系:

for(String url: urls) if(url.startsWith(input) {doSomething();}

现在我知道在Hash Set中,函数"contains()"在"O(1)"中起作用,但是没有"containsPrefix()".有没有像Lucene这样的大型图书馆或自己编写的简单方法？我没有问题这样做但是对于这样一个简单的问题似乎有点过头了所以我想知道是否有现成的简单解决方案:-)

从我的计算机科学课程中,我记得一个由字符串片段组成的树,但我忘了它是如何调用的.它的工作方式如下:

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

PS:我如何调用返回字符串为前缀的所有字符串的方法？就像a是b的前缀一样,b是什么？

Answer 1

如果您需要有效地查找字符串的前缀，请使用 Trie ，这是一种专门为此目的而设计的数据结构：

trie（或前缀树）是一种有序树数据结构，用于存储关联数组，其中键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的键；相反，它在树中的位置定义了与其关联的键。节点的所有后代都有与该节点关联的字符串的公共前缀，并且根与空字符串关联

两个带有示例 实现的链接。