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

在開(kāi)發(fā)過(guò)程中，遇到一個(gè)情況，就是從所有騎手Id中過(guò)濾沒(méi)有標(biāo)簽的騎手Id（直接查詢沒(méi)有標(biāo)簽的騎手不容易實(shí)現(xiàn)），

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

邏輯很簡(jiǎn)單，就是取一個(gè)差集，這樣子就拿到?jīng)]有任何標(biāo)簽的騎手?jǐn)?shù)據(jù)。

但是在實(shí)際開(kāi)發(fā)過(guò)程中，removeAll這個(gè)動(dòng)作很耗時(shí)，做測(cè)試大概要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)原來(lái)的list
  if (c.contains(elementData[r]) complement) // 這里調(diào)用contains方法
  elementData[w++] = elementData[r];
 } finally {
 ....
 }
 return modified;
}

在循環(huán)過(guò)程中調(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;
}

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

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

下面看一下最終的實(shí)現(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迭代器進(jìn)行數(shù)據(jù)的操作

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

同樣數(shù)量級(jí)list, 整個(gè)過(guò)程只需要幾十毫秒，簡(jiǎn)直天壤之別。

回過(guò)頭來(lái)，比較一下兩種實(shí)現(xiàn)方式，為什么差距這個(gè)大。

1、外層循環(huán)

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

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

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

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

接下來(lái)我們簡(jiǎn)單看一下hash表。

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

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

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

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

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論