我有这个。
private ArrayList<String> words;
这是一本字典，所以单词已经排序。根据旧的研究，我知道二项式搜索应该非常非常快，我想 Java 已经实现了必要的功能。
那么，查找某个字符串是否存在于已排序的ArrayList 中的最有效方法是什么？或者我应该使用不同的类型？
谢谢你。
问问题
192 次
4 回答
8
或者我应该使用不同的类型？
尝试使用 aHashSet<String>代替。假设没有太多哈希冲突，它的contains方法具有 O(1) 查找。从文档中：
此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在桶中。
对排序的二进制搜索ArrayList只有 O(log n)。这仍然非常快，但不如使用HashSet.
于 2013-01-15T14:57:00.957 回答
3
二进制搜索将是排序数组中最快的。如果您使用哈希集，则可以在恒定时间内完成对存在性的测试。
于 2013-01-15T14:57:45.993 回答
2
取决于您要尝试查找特定字符串的次数。您可能想尝试 a HashMap<String, String>，因为随着地图的增长，这将保持快速。
于 2013-01-15T14:57:29.690 回答
1
如果您要进行二进制搜索，我建议您将数据重新组织成Binary Search Tree
ArrayLists 通常用于顺序操作和随机访问。如果您要进行搜索并希望以最快的速度查找，那么最好从一开始就组织您的数据。这还具有促进更快插入/移除以及您希望在尽可能快的时间内完成的所有其他操作的优势。
谷歌和其他地方有大量指南可以帮助您入门。
于 2013-01-15T14:59:28.367 回答