java - Java ArrayList 中的 contains() 方法是否使用二进制搜索？

Question

Java ArrayList 中的 contains() 方法是否使用二进制搜索？还是我需要使用 Collections 来代替？

Answer 1

不，您需要Collections使用二进制搜索，通常在排序之后。AnArrayList对其排序一无所知，并且您必须知道列表已排序，然后才能使用二进制搜索。

或者，您可以使用TreeSet，这与使用二进制搜索一样有效。

Answer 2

不，它不使用二进制搜索，因为列表不必排序。

使用 Collections 类的实用方法首先对列表进行排序，然后执行二进制搜索。

Answer 3

不，这意味着在每次插入时都会增加开销，因此不包括在内。

这是源代码：它只是测试所有值：

218     public boolean contains(Object o) {
219         return indexOf(o) >= 0;
220     }

229     public int indexOf(Object o) {
230         if (o == null) {
231             for (int i = 0; i < size; i++)
232                 if (elementData[i]==null)
233                     return i;
234         } else {
235             for (int i = 0; i < size; i++)
236                 if (o.equals(elementData[i]))
237                     return i;
238         }
239         return -1;
240     }

Answer 4

不，您需要使用 Collections 才能使用二进制搜索，通常是在对其进行排序之后。