Java中ArrayList的removeAll方法詳解

本文介紹的是關(guān)于Java中ArrayList的removeAll方法的相關(guān)內(nèi)容，分享出來供大家參考學習，下面來一起看看詳細的介紹：

在開發(fā)過程中，遇到一個情況，就是從所有騎手Id中過濾沒有標簽的騎手Id（直接查詢沒有標簽的騎手不容易實現(xiàn)），

List<Integer> allRiderIdList = new ArrayList(); // 所有的騎手，大致有23W數(shù)據(jù)
List<Integer> hasAnyTagRiderId = new ArrayList(); // 有標簽的騎手， 大致有21W數(shù)據(jù)
List<Integer> withoutAnyTagRiderList = allRiderIdList.removeAll(hasAnyTagRiderId);

邏輯很簡單，就是取一個差集，這樣子就拿到?jīng)]有任何標簽的騎手數(shù)據(jù)。

但是在實際開發(fā)過程中，removeAll這個動作很耗時，做測試大概要4分鐘左右。查看ArrayList中removeAll的源碼片段：

public boolean removeAll(Collection<?> c) {
 Objects.requireNonNull(c);
 return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
 final Object[] elementData = this.elementData;
 int r = 0, w = 0;
 boolean modified = false;
 try {
 for (; r < size; r++) // 循環(huán)原來的list
  if (c.contains(elementData[r]) complement) // 這里調(diào)用contains方法
  elementData[w++] = elementData[r];
 } finally {
 ....
 }
 return modified;
}

在循環(huán)過程中調(diào)用contains方法做比較，查一下ArrayList的contains方法，源代碼片段如下：

public boolean contains(Object o) {
 return indexOf(o) >= 0;
}

public int indexOf(Object o) {
 if (o null) {
 for (int i = 0; i < size; i++)
  if (elementData[i]==null)
  return i;
 } else {
 for (int i = 0; i < size; i++)
  if (o.equals(elementData[i]))
  return i;
 }
 return -1;
}

這可以看出來，在比較的過程中，又調(diào)用了一次循環(huán)。

所以removeAll兩層for循環(huán)，復雜度O(m*n)，所以在操作比較大的ArrayList時，這種方法是絕對不可取的。

下面看一下最終的實現(xiàn)方式：

private List<Integer> removeAll(List<Integer> src, List<Integer> target) {
 LinkedList<Integer> result = new LinkedList<>(src); //大集合用linkedlist
 HashSet<Integer> targetHash = new HashSet<>(target); //小集合用hashset
 Iterator<Integer> iter = result.iterator(); //采用Iterator迭代器進行數(shù)據(jù)的操作

 while(iter.hasNext()){ 
 if(targetHash.contains(iter.next())){
  iter.remove();
 }
 }
 return result;
}

同樣數(shù)量級list, 整個過程只需要幾十毫秒，簡直天壤之別。

回過頭來，比較一下兩種實現(xiàn)方式，為什么差距這個大。

1、外層循環(huán)

     一個是普通的for循環(huán)，一個迭代器遍歷元素，二者相差不大

2、內(nèi)層數(shù)據(jù)比較

     前者通過index方法把整個數(shù)組順序遍歷了一遍;

     后者調(diào)用HashSet的contains方法，實際上是調(diào)用HashMap的containKey方法，查找時是通過hash表查找，復雜度為O(1)。

接下來我們簡單看一下hash表。

hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關(guān)鍵字進行比較來進行查找。這個源于Hash表設(shè)計的特殊性，它采用了函數(shù)映射的思想將記錄的存儲位置與記錄的關(guān)鍵字關(guān)聯(lián)起來，從而能夠很快速地進行查找?？梢院唵卫斫鉃椋钥臻g換時間，犧牲空間復雜度來換取時間復雜度。

hash表采用一個映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計算出該記錄在表中的存儲位置，通常情況下，這種映射關(guān)系稱作為hash函數(shù)，而通過hash函數(shù)和關(guān)鍵字計算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置，并不是實際的物理地址)稱作為hash地址。

上面的圖大家應該都很熟悉，hash表的一種實現(xiàn)方式，是由數(shù)組+鏈表組成的。元素放入hash表的位置通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。

另外hash表大小的確定也很關(guān)鍵，如果hash表的空間遠遠大于最后實際存儲的記錄個數(shù)，則造成了很大的空間浪費，如果選取小了的話，則容易造成沖突。在實際情況中，一般需要根據(jù)最終記錄存儲個數(shù)和關(guān)鍵字的分布特點來確定Hash表的大小。還有一種情況時可能事先不知道最終需要存儲的記錄個數(shù)，則需要動態(tài)維護Hash表的容量，此時可能需要重新計算Hash地址。
當然，關(guān)于hash表要說的話太多，先簡單到此吧~~~

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對億速云的支持。