在ArrayList <String>中查找

Question

我有这个.

private ArrayList<String> words;

这是一本字典,所以单词已经排序了.通过旧的研究,我知道二项式搜索应该非常快,我想Java已经实现了必要的.

那么,查找排序的 ArrayList中是否存在某个字符串的最有效方法是什么？或者我应该使用不同的类型？

谢谢.

Answer 1

或者我应该使用不同的类型？

尝试使用HashSet<String>替代品.它的contains方法有O(1)查找,假设没有太多的哈希冲突.从文档:

该类为基本操作(添加,删除,包含和大小)提供恒定的时间性能,假设散列函数在桶之间正确地分散元素.

对已排序的二进制搜索ArrayList仅为O(log n).这仍然非常快,但它没有使用a那么快HashSet.