Java中查找16元素小型无序整数数组目标值的最高效方法

针对固定长度仅16的小型无序整数数组，普通for循环线性遍历是综合性能、可靠性、实现成本最优的方案，没有之一。小数据量场景下不要硬套算法复杂度公式，实际执行的常数项开销才是决定性能的核心。

各候选方案实测分析 #

• 普通for循环遍历
  这个方案没有任何前置预处理开销，没有额外对象分配，最坏情况仅需要做16次整数比较。JIT编译时会自动对这种短固定长度循环做循环展开优化，甚至直接生成无循环的逐元素比较指令，CPU分支预测命中率极高，是所有方案里执行效率最高的。
  正确实现代码：

  public static boolean contains(int[] arr, int target) {
      for (int num : arr) {
          if (num == target) {
              return true;
          }
      }
      return false;
  }
  

  不管是用下标遍历还是增强for循环，JIT优化后的执行效率几乎没有差异。
• 排序后调用Arrays.binarySearch二分查找
  这个方案在单次/少量查询场景下是纯负优化。仅给16个元素排序的开销（元素交换、分支判断、排序逻辑本身的成本）就已经远高于直接遍历16次比较的开销，哪怕后续二分查找只需要4次比较，前置排序的成本也需要几十次查询才能摊薄。如果不是对同一个固定静态数组做几十上百次重复查询，完全不需要考虑这个方案。
• 调用Arrays.asList(arr).contains(targetVal)或全程用List存储
  首先这个写法对原始类型int[]存在正确性bug：Arrays.asList接收可变对象参数，传入原始类型数组时，会把整个数组当成一个单独元素存到List里，返回的List长度固定为1，调用contains只会判断目标值是否和数组对象本身相等，根本不会遍历数组元素，逻辑完全错误。
  就算你正确完成原始类型到包装类的转换，或者全程用ArrayList<Integer>存储数据，List.contains本质也是内部做线性遍历，但是多了Integer装箱拆箱、引用间接寻址的额外开销，实测性能比直接遍历原始int数组低2~5倍，没有任何性能优势。

其他可选方案的适用边界 #

不存在通用的更优实现，所有带额外预处理、额外内存占用的方案都只适合特定场景：

• 如果你需要对同一个固定不变的数组做超高频次查询（比如每秒几十万次调用），且数组内整数的取值范围不大，可以提前把元素映射到BitSet或者定长boolean[]哈希桶中，单次查询可以做到O(1)时间复杂度，性能比线性遍历更高。
• 如果整数取值范围跨度极大，用HashSet<Integer>存储元素的方案完全不划算：哈希值计算、哈希桶寻址、Node对象分配、装箱拆箱的开销，比直接遍历16个元素高一个数量级，纯纯负优化。

核心提醒：对于长度小于30的小型集合，所有需要额外分配对象、做预处理的方案，性能基本都打不过最简单的线性遍历，不要为了用所谓的“高级算法/数据结构”强行增加不必要的开销。

内容的提问来源于stack exchange，提问作者boingy