检查String是否存在的高效数据结构

Question

我正在编写一个程序,它将为数据结构添加越来越多的数字或唯一的字符串.一旦完成,我后来需要不断检查其中是否存在字符串.

如果我使用ArrayList,我相信检查某些指定字符串的存在会遍历所有项目,直到找到匹配的字符串(或到达结尾并返回false).

但是,使用HashMap我知道在常量时间我可以简单地将键用作String并返回任何非null对象,从而使此操作更快.但是,我并不热衷于填充HashMap,其值完全是任意的.是否存在使用散列函数的现成数据结构,但不需要放置值？

Answer 1

如果我要使用ArrayList,我相信检查某些指定字符串的存在会遍历所有项目,直到找到匹配的字符串

正确,检查项目列表是列表条目数的线性.

但是,我并不热衷于填充HashMap,其值完全是任意的

您不必:Java提供了一个HashSet<T>类,它非常类似于HashMap没有值的部分.

您可以将所有字符串放在那里,然后在恒定时间内检查是否存在其他字符串;

Set<String> knownStrings = new HashSet<String>();
... // Fill the set with strings

if (knownString.contains(myString)) {
    ...
}

Answer 2

这取决于很多因素,包括你必须输入到该数据结构中的字符串数量(你知道这个数字是提前的,还是有一个基本的想法？),以及你期望的命中/未命中率.

一个非常有效的数据结构是trie或radix树; 它们基本上是为此而制造的.有关它们如何工作的说明,请参阅维基百科条目(基本树定义的后续内容在此页面中).有Java实现(其中一个在这里 ;但是我有一组固定的字符串要注入,这就是我使用构建器的原因).

如果您的琴弦数量非常庞大并且您没有想到最小的失误率,那么您也可以考虑使用布隆过滤器 ; 但问题是它是概率性的; 但你可以得到"不存在"的快速答案.这里也有Java实现(Guava有一个实现).

否则,好吧,HashSet......