java - Java集合中的搜索算法

Question

这个问题可能已经得到解答。不过我没找到。

在Java Collections中，我总是使用Collections.sort(coll)，然后进行搜索。我的问题是集合将始终执行二分搜索还是内部决定的。集合是否存储任何标识符来决定线性搜索和二分搜索。

Answer 1

当您查看 Collections.sort(coll) 的 Java 8 源代码时，它使用 Arrays.sort(Object[] a) 方法。如果您不将 java.util.Arrays.useLegacyMergeSort 作为系统属性传递。否则，它使用传统的合并排序。

Arrays.sort(Object[] a) 使用 TimSort，这是一种策略算法，根据给定数组的顺序和大小选择插入排序或合并排序。您可以在以下链接中找到详细信息:

• https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-java.lang.Object:A-
• https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399