如何從兩個List中篩選出相同的值

假設現有社保卡和身份證若干，想要匹配篩選出一一對應的社保卡和身份證。

轉換為List<社保卡> socialList,和List idList，從二者中找出匹配的社保卡。

模型

創建社保卡類:

創建身份證類:

最簡單的辦法：遍歷

只要做兩輪循環即可。

準備初始化數據：

遍歷

很容易看出，時間複雜度O(m,n)=m*n.

採用Hash

通過觀察發現，兩個list取相同的部分時，每次都遍歷兩個list。那麼，可以把判斷條件放入Hash中，判斷hash是否存在來代替遍歷查找。

如此，假設hash演算法特別好，hash的時間複雜度為O(n)=n。如此推出這種做法的時間複雜度為O(m,n)=2m+n. 當然，更重要的是這種寫法更讓人喜歡，天然不喜歡嵌套的判斷，喜歡扁平化的風格。

Hash一定會比遍歷快嗎

想當然的以為，hash肯定會比遍歷快，因為是hash啊。其實，可以算算比較結果。比較什麼時候

2m+n < m*n

從數據歸納法的角度，n必須大於2，不然即演變程

2m+2 < 2m

於是，當n>2時：

結果是：

m=2,n=3
3

也就是說n<=3的時候，遍歷要比hash快。事實上還要更快，因為hash還需要創建更多的對象。然而，大部分情況下，n也就是第二個數組的長度是大於3的。這就是為什麼說hash要更好寫。當然，另一個很重要的原因是lambda stream的運算符號遠比嵌套循環讓人喜愛。

· 2017年【中公教育】特別推出2017年就業促進計劃，500萬就業基金助你成為IT達人

詳情請戳http：//www.ujiuye.com/zt/jycj/?wt.bd=bgz

· 什麼？海量IT學習資料白給你都不要？別想了，加群搶：584539956

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！