Java ArrayList 中的 contains() 方法是否使用二分查找？

Question

Java ArrayList中的contains()方法是否使用二分查找？还是我需要使用Collections来代替呢？

- John Roberts

---

你知道Java是开源的，你可以查看contains()方法的代码，嗯？ - Juvanis

Answer 1

不，你需要使用 Collections 在排序后使用二分查找。一个 ArrayList 对它的顺序一无所知，你必须知道一个列表被排序过才能使用二分查找。

或者，你可以使用 TreeSet，它与使用二分查找一样有效。

- Louis Wasserman

Answer 2

不，它不使用二分查找，因为列表不需要排序。

使用Collections类的实用方法首先对列表进行排序，然后执行二分查找。

- Puce

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     }

- Denys Séguret

Answer 4

不，你需要使用集合来使用二分查找，通常是在排序后进行。

- samba