如何在Java中创建简单的前缀索引？
我有大量的url，我想实现自动完成。 我不喜欢天真方法的复杂性，因为它与设定大小呈线性关系：
for(String url: urls) if(url.startsWith(input) {doSomething();} 现在我知道在哈希集中，函数“contains（）”在“O（1）”中工作，但是没有“containsPrefix（）”。 有没有像Lucene这样的大型图书馆或自己编写的简单方法？ 我会毫无困难地做这件事，但对于这样一个简单的问题来说似乎有些过分，所以我想知道是否有现成的简单解决方案:-)
从我的计算机科学课程中我记得一个由字符串片段组成的树，但我忘了它是如何被调用的。 它的工作方式如下：
[car, care, carrot,carrotville]-> car | -/ -e -rrot | ----ville
PS：我如何调用返回字符串为前缀的所有字符串的方法？ 就像a是b的前缀一样，b是什么？
如果您需要有效地查找字符串的前缀，请使用Trie ，一种专为此目的而设计的数据结构：
trie或前缀树是一种有序树数据结构，用于存储关键数组，其中键通常是字符串。 与二叉搜索树不同，树中没有节点存储与该节点关联的密钥; 相反，它在树中的位置定义了与之关联的键。 节点的所有后代都具有与该节点关联的字符串的公共前缀，并且根与空字符串相关联
两个链接与示例 实现 。
很久以前我在这里放了一个简单的Trie实现：
http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java
然而，这不是一个紧凑的Trie，因此它为每个字符创建一个节点，创建一个紧凑的节点有点棘手。
一个很好的替代算法是三元搜索树 （更高效的内存） https://github.com/varunpant/TernaryTree/tree/master/TernaryTree
这是java中的trie http://algs4.cs.princeton.edu/52trie/TrieST.java.html
Regexp实现java.util.regex.Pattern可以有效地处理前缀：
StringBuilder buffer = new StringBuilder(); for (String prefix : prefixes) { if (buffer.length() > 0) buffer.append("|"); buffer.append(prefix); } Pattern prefixPattern = Pattern.compile("^(" + buffer + ")");
您可以测试所有前缀：
boolean containsPrefix = prefixPattern.matcher(stringToTest).find();
注意：为简单起见，前缀字符串不会被转义。 正则表达式字符[，]，\，*，？，$，^，（，），{，}和| 必须以\为前缀。