99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

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

站在用戶的角度思考問題，與客戶深入溝通，找到珠海網(wǎng)站設(shè)計(jì)與珠海網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：做網(wǎng)站、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋珠海地區(qū)。

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

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

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

但是在實(shí)際開發(fā)過程中，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)原來的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)，復(fù)雜度O(m*n)，所以在操作比較大的ArrayList時(shí)，這種方法是絕對(duì)不可取的。

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

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

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

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

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

1、外層循環(huán)

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

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

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

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

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

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

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

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

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

總結(jié)

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