作者 | 沉默王二
責編 | Elle
在逛 programcreek 的時候，我發現了一些專注細節但價值連城的主題。比如說：如何檢查Java數組中是否包含某個值 ？像這類靈魂拷問的主題，非常值得深入地研究一下。
另外，我想要告訴大家的是，作為程式設計師，我們千萬不要輕視這些基礎的知識點。因為基礎的知識點是各種上層技術共同的基礎，只有徹底地掌握了這些基礎知識點，才能更好地理解程序的運行原理，做出更優化的產品。
我曾在某個技術論壇上分享過一篇非常基礎的文章，結果遭到了無數的嘲諷：「這麼水的文章不值得分享。」我點開他的頭像進入他的主頁，發現他從來沒有分享過一篇文章，不過倒是在別人的博客下面留下過不少的足跡，大多數都是冷嘲熱諷。我就納悶了，技術人不都應該像我這樣低調謙遜嗎？怎麼戾氣這麼重！
好了，讓我們來步入正題。如何檢查數組（未排序）中是否包含某個值 ？這是一個非常有用並且經常使用的操作。我想大家的腦海中應該已經浮現出來了幾種解決方案，這些方案的時間複雜度可能大不相同。
我先來提供四種不同的方法，大家看看是否高效。
1）使用 List
publicstaticbooleanuseList(String[] arr, String targetValue){return Arrays.asList(arr).contains(targetValue);}
Arrays 類中有一個內部類 ArrayList（可以通過 Arrays.asList(arr) 創建該實例），其 contains() 方法的源碼如下所示。
public boolean contains(Object o) {return indexOf(o) != -1;}publicintindexOf(Object o) { E[] a = this.a;if (o == null) {for (int i = 0; i < a.length; i++)if (a[i] == null)return i; } else {for (int i = 0; i < a.length; i++)if (o.equals(a[i]))return i; }return-1;}
從上面的源碼可以看得出，contains() 方法調用了 indexOf() 方法，如果返回 -1 則表示 ArrayList 中不包含指定的元素，否則就包含。其中 indexOf() 方法用來獲取元素在 ArrayList 中的下標，如果元素為 null，則使用「==」操作符進行判斷，否則使用 equals() 方法進行判斷。
PS：關於「==」操作符和 equals() 方法，可以參照我另外一篇文章《如何比較 Java 的字符串？》
2）使用 Set
public static boolean useSet(String[] arr, String targetValue) {Set<String> set = new HashSet<String>(Arrays.asList(arr));returnset.contains(targetValue);}
HashSet 其實是通過 HashMap 實現的，當使用 new HashSet<String>(Arrays.asList(arr)) 創建並初始化了 HashSet 對象後，其實是在 HashMap 的鍵中放入了數組的值，只不過 HashMap 的值為默認的一個擺設對象。大家感興趣的話，可以查看一下 HashSet 的源碼。
我們來著重看一下 HashSet 的 contains() 方法的源碼。
publicbooleancontains(Object o){return map.containsKey(o);}publicbooleancontainsKey(Object key){return getNode(hash(key), key) != null;}
從上面的源碼可以看得出，contains() 方法調用了 HashMap 的 containsKey() 方法，如果指定的元素在 HashMap 的鍵中，則返回 true；否則返回 false。
3）使用一個簡單的循環
publicstatic boolean useLoop(String[] arr, String targetValue) {for (String s : arr) {if (s.equals(targetValue))returntrue; }returnfalse;}
for-each 循環中使用了 equals() 方法進行判斷——這段代碼讓我想起了幾個詞，分別是簡約、高效、清晰。
4）使用 Arrays.binarySearch()
publicstaticbooleanuseArraysBinarySearch(String[] arr, String targetValue){int a = Arrays.binarySearch(arr, targetValue);if (a > 0)returntrue;elsereturnfalse;}
不過，binarySearch() 只適合查找已經排序過的數組。
由於我們不確定數組是否已經排序過，所以我們先來比較一下前三種方法的時間複雜度。由於調用 1 次的時間太短，沒有統計意義，我們就模擬調用 100000 次，具體的測試代碼如下所示。
String[] arr = new String[]{"沉", "默", "王", "二", "真牛逼"};// 使用 Listlong startTime = System.nanoTime();for (int i = 0; i < 100000; i++) { useList(arr, "真牛逼");}long endTime = System.nanoTime();long duration = endTime - startTime;System.out.println("useList: " + duration / 1000000);// 使用 SetstartTime = System.nanoTime();for (int i = 0; i < 100000; i++) { useSet(arr, "真牛逼");}endTime = System.nanoTime();duration = endTime - startTime;System.out.println("useSet: " + duration / 1000000);// 使用一個簡單的循環startTime = System.nanoTime();for (int i = 0; i < 100000; i++) { useLoop(arr, "真牛逼");}endTime = System.nanoTime();duration = endTime - startTime;System.out.println("useLoop: " + duration / 1000000);
PS：nanoTime() 獲取的是納秒級，這樣計算的時間就更精確，最後除以 1000000 就是毫秒。換算單位是這樣的：1秒=1000毫秒，1毫秒=1000微秒，1微秒=1000納秒。
統計結果如下所示：
useList: 6useSet: 40useLoop: 2
假如把數組的長度增加到 1000，我們再來看一下統計結果。
String[] arr = newString[1000];Random s = new Random();for(int i=0; i< 1000; i++){ arr[i] = String.valueOf(s.nextInt());}
這時數組中是沒有我們要找的元素的。為了做比較，我們順便把二分查找也添加到統計項目中。
// 使用二分查找startTime = System.nanoTime();for (int i = 0; i < 100000; i++) { useArraysBinarySearch(arr, "真牛逼");}endTime = System.nanoTime();duration = endTime - startTime;System.out.println("useArraysBinarySearch: " + duration / 1000000);統計結果如下所示：useList: 91useSet: 1460useLoop: 70useArraysBinarySearch: 4
我們再把數組的長度調整到 10000。
String[] arr = newString[10000];Random s = new Random();for(int i=0; i< 10000; i++){ arr[i] = String.valueOf(s.nextInt());}
統計結果如下所示：
useList: 1137useSet: 15711useLoop: 1115useArraysBinarySearch: 5
從上述的統計結果中可以很明顯地得出這樣一個結論：使用簡單的 for 循環，效率要比使用 List 和 Set 高。這是因為把元素從數組中讀出來再添加到集合中，就要花費一定的時間，而簡單的 for 循環則省去了這部分時間。
在得出這個結論之前，說實話，我最喜歡的方式其實是第一種「使用 List」，因為只需要一行代碼 Arrays.asList(arr).contains(targetValue) 就可以搞定。
雖然二分查找（Arrays.binarySearch()）花費的時間明顯要少得多，但這個結論是不可信的。因為二分查找明確要求數組是排序過的，否則查找出的結果是沒有意義的。可以看一下官方的 Javadoc。
Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object []) method) prior to making this call. If it is not sorted, the results are undefined.
實際上，如果要在一個數組或者集合中有效地確定某個值是否存在，一個排序過的 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 實現的）。哈希表是通過哈希函數來映射的，所以拿到一個關鍵字，通過哈希函數轉換一下，就可以直接從表中取出對應的值——一次直達。
好了各位讀者朋友們，以上就是本文的全部內容了。能看到這裡的都是最優秀的程式設計師，我必須要為大家點個讚。
聲明：本文為作者投稿，版權歸作者個人所有。
【End】