• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

如何高效判断Java数组是否包含某个值

Java基础 tiantian 3941次浏览 0个评论 扫描二维码

在Java中,我们如何判断一个未排序数组中是否包含一个特定的值?这在Java代码中是一个频繁且非常实用的操作。那么什么样的方法才是最高效的方式?当然,这个问题在 Stack Overflow 也是得票率非常高的一个问答。得票率排在前面的几个答案给出了几种不同的方法,但是它们的时间复杂度却相差甚远。本文将详细地探讨主流的方法,并给出它们各自的时间损耗。

如何高效判断Java数组是否包含某个值

四种方法

List

public static boolean useList(String[] arr, String value) {
return Arrays.asList(arr).contains(value);
}
Set

public static boolean useSet(String[] arr, String value) {
Set<String> sets = new HashSet<>(Arrays.asList(arr));
return sets.contains(value);
}
loop

public static boolean useLoop(String[] arr, String value) {
for (String s : arr) {
if (s.equals(value)) return true;
}
return false;
}
binarySearch

public static boolean useBinarySearch(String[] arr, String value) {
int result = Arrays.binarySearch(arr, value);
if (result > 0) return true;
else return false;
}

此方法是不正确的,因为Arrays的binarySearch方法必须应用于有序数组。

性能对比

如果读者熟悉以上Java代码片段中出现的几种数据结构,那么可以利用时间复杂度计算标准,先推算出这四种方式的性能对比的大致结果。当然,我们这里不采用这种方式,而是直接运用如下测试代码来对比这四种方式的时间损耗情况。为了使得我们的测试结果更具有代表性,我们针对不同的数据量做了多组测试。也许,这个测量方式并不精确,但测量结果是清晰和可信任的。测试的示例代码如下:

public static void main(String[] args) {

String[] arr = new String[] { “www.”, “tiantian”, “bian”, “ma”, “.com”};

long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
// use list
useList(arr, “天天编码”);
// use set
//useSet(arr, “天天编码”);
// use loop
//useLoop(arr, “天天编码”);
// use binarySearch
//useBinarySearch(arr, “天天编码”);
long endTime = System.nanoTime();
long duration = endTime = startTime;
System.out.println(“useList : ” + duration / 1000000);

}

读者可以自己先推算一下测试结果,再上机验证结果。我自己的上级验证如下:

数组长度 方法 运行耗时 数组长度 方法 运行耗时
5 list 13 100 list 50
5 set 72 100 set 668
5 loop 5 100 loop 47
5 binarySearch 9 100 binarySearch 8
1k list 112 10k list 1590
1k set 2055 10k set 23819
1k loop 99 10k loop 1526
1k binarySearch 12 10k binarySearch 12

总结

参照这个表格,结论已经很明显了。最简单的Loop方法比其他任何使用集合容器的方法都更加高效。很多的开源项目代码显示,很多Java开发者喜欢使用第一种方法(list),实际上,该方法的性能并不好。该方法把一个数组的元素转移到一个新的集合容器中,显然,在所有的元素转移完成之前,新的集合容器处于不可用的状态。

该表格还反映出一个事实:Arrays.binarySearch()方法的性能是最好的,特别是对于数组长度很大的数组。但是该方法要求数组必须有序,这限制住了该方法的使用场景,本文实例代码中的数组并不是有序的,所以不应该使用该方法。

实际上,如果你确实需要高效地检查某个特定值是否被包含在某些数组或者集合容器中,你应该考虑使用有序列表或有序树,这些集合容器查找特定值的时间复杂度是 O(log(n))。当然,如果使用哈希集合,时间复杂度下降为 O(1)


天天编码 , 版权所有丨本文标题:如何高效判断Java数组是否包含某个值
转载请保留页面地址:http://www.tiantianbianma.com/java-array-include-value.html/
喜欢 (8)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址