灵魂拷问：如何检查Java数组中是否包含某个值？
如何检查数组（未排序）中是否包含某个值 ？这是一个非常有用并且经常使用的操作。我想大家的脑海中应该已经浮现出来了几种解决方案，这些方案的时间复杂度可能大不相同。
我先来提供四种不同的方法，大家看看是否高效。
1）使用 List
Arrays 类中有一个内部类 ArrayList（可以通过 Arrays.asList(arr) 创建该实例），其 contains() 方法的源码如下所示。
从上面的源码可以看得出，contains() 方法调用了 indexOf() 方法，如果返回 -1 则表示 ArrayList 中不包含指定的元素，否则就包含。其中 indexOf() 方法用来获取元素在 ArrayList 中的下标，如果元素为 null，则使用“==”操作符进行判断，否则使用 equals() 方法进行判断。
PS：关于“==”操作符和 equals() 方法，可以参照我另外一篇文章《如何比较 Java 的字符串？》
2）使用 Set
HashSet 其实是通过 HashMap 实现的，当使用 new HashSet(Arrays.asList(arr)) 创建并初始化了 HashSet 对象后，其实是在 HashMap 的键中放入了数组的值，只不过 HashMap 的值为默认的一个摆设对象。大家感兴趣的话，可以查看一下 HashSet 的源码。
我们来着重看一下 HashSet 的 contains() 方法的源码。
从上面的源码可以看得出，contains() 方法调用了 HashMap 的 containsKey() 方法，如果指定的元素在 HashMap 的键中，则返回 true；否则返回 false。
3）使用一个简单的循环
for-each 循环中使用了 equals() 方法进行判断——这段代码让我想起了几个词，分别是简约、高效、清晰。
4）使用 Arrays.binarySearch()
不过，binarySearch() 只适合查找已经排序过的数组。
由于我们不确定数组是否已经排序过，所以我们先来比较一下前三种方法的时间复杂度。由于调用 1 次的时间太短，没有统计意义，我们就模拟调用 100000 次，具体的测试代码如下所示。
PS：nanoTime() 获取的是纳秒级，这样计算的时间就更精确，最后除以 1000000 就是毫秒。换算单位是这样的：1秒=1000毫秒，1毫秒=1000微秒，1微秒=1000纳秒。
统计结果如下所示：
假如把数组的长度增加到 1000，我们再来看一下统计结果。
这时数组中是没有我们要找的元素的。为了做比较，我们顺便把二分查找也添加到统计项目中。
统计结果如下所示：
我们再把数组的长度调整到 10000。
统计结果如下所示：
从上述的统计结果中可以很明显地得出这样一个结论：使用简单的 for 循环，效率要比使用 List 和 Set 高。这是因为把元素从数组中读出来再添加到集合中，就要花费一定的时间，而简单的 for 循环则省去了这部分时间。
在得出这个结论之前，说实话，我最喜欢的方式其实是第一种“使用 List”，因为只需要一行代码 Arrays.asList(arr).contains(targetValue) 就可以搞定。
虽然二分查找（Arrays.binarySearch()）花费的时间明显要少得多，但这个结论是不可信的。因为二分查找明确要求数组是排序过的，否则查找出的结果是没有意义的。
实际上，如果要在一个数组或者集合中有效地确定某个值是否存在，一个排序过的 List 的算法复杂度为 O(logn)，而 HashSet 则为 O(1)。
我们再来发散一下思维：怎么理解 O(logn) 和 O(1) 呢？
O(logn) 的算法复杂度，比较典型的例子是二分查找。举个例子，假设现在一堆试卷，已经按照分数从高到底排列好了。现在要查找有没有 79 分的试卷，怎么办呢？可以先从中间找起，因为按照 100 分的卷子来看，79 分大差不差应该就在中间的位置（平均分如果低于 79 说明好学生就比较少了），如果中间这份卷子的分数是 83，那说明 79 分的卷子就在下面的一半，这时候可以把上面那半放在一边了。然后按照相同的方式，每次就从中间开始找，直到找到 79 分的卷子（当然也可能没有 79 分）。
假如有 56 份卷子，找一次，还剩 28 份，再找一次，还剩 14 份，再找一次，还剩 7 份，再找一次，还剩 2 或者 3 份。如果是 2 份，再找一次，就只剩下 1 份了；如果是 3 份，就还需要再找 2 次。
我们知道，log2(32) = 5，log2(64) = 6，而 56 就介于 32 和 64 之间。也就是说，二分查找大约需要 log2(n) 次才能“找到”或者“没找到”。而在算法复杂度里，经常忽略常数，所以不管是以 2 为底数，还是 3 为底数，统一写成 log(n) 的形式。
再来说说 O(1)，比较典型的例子就是哈希表（HashSet 是由 HashMap 实现的）。哈希表是通过哈希函数来映射的，所以拿到一个关键字，通过哈希函数转换一下，就可以直接从表中取出对应的值——一次直达。
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20191218A06RBA00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
