java - 在 ArrayList 中查找

Question

我有这个。

private ArrayList<String> words;

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

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

谢谢。

Answer 1

Or should I use a different type?

尝试使用 HashSet<String>反而。它的contains假设没有太多的散列冲突，方法具有 O(1) 查找。来自文档:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

对已排序的 ArrayList 进行二分查找仅为 O(log n)。这仍然非常快，但不如使用 HashSet 快。 .