日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
記一次集合去重導致的線上問題

前言

10年積累的成都網(wǎng)站制作、成都做網(wǎng)站經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先做網(wǎng)站設計后付款的網(wǎng)站建設流程，更有交口免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

在工作中一次排查慢接口時，查到了一個函數(shù)耗時較長，最終定位到是通過 List 去重導致的。

由于測試環(huán)境還有線上早期數(shù)據(jù)較少，這個接口的性能問題沒有引起較大關(guān)注，后面頻繁超時，才引起重視。

之前看《阿里巴巴Java開發(fā)手冊》里面有這樣一段描述：

你看，阿里前輩們都免費總結(jié)了，不過還是會看到有人會用List的contains函數(shù)來去重......

不記得的，罰抄10萬遍

如果需要這本書資源的網(wǎng)上下載也行，私聊我發(fā)你也行

今天我就結(jié)合源碼聊聊Set是怎樣保證數(shù)據(jù)的唯一性的，為什么兩種去重方式性能差距這么大

HashSet源碼

先看看類注釋：

看類注釋上，我們可以得到的信息有：

  • 底層實現(xiàn)基于 HashMap，所以迭代時不能保證按照插入順序，或者其它順序進行迭代;
  • add、remove、contanins、size 等方法的耗時性能，是不會隨著數(shù)據(jù)量的增加而增加的，這個主要跟 HashMap 底層的數(shù)組數(shù)據(jù)結(jié)構(gòu)有關(guān)，不管數(shù)據(jù)量多大，不考慮 hash 沖突的情況下，時間復雜度都是 O (1);
  • 線程不安全的，如果需要安全請自行加鎖，或者使用 Collections.synchronizedSet;
  • 迭代過程中，如果數(shù)據(jù)結(jié)構(gòu)被改變，會快速失敗的，會拋出 ConcurrentModificationException 異常。

剛才是從類注釋中看到，HashSet 的實現(xiàn)是基于 HashMap 的，在 Java 中，要基于基礎類進行創(chuàng)新實現(xiàn)，有兩種辦法：

  • 繼承基礎類，覆寫基礎類的方法，比如說繼承 HashMap , 覆寫其 add 的方法;
  • 組合基礎類，通過調(diào)用基礎類的方法，來復用基礎類的能力。

HashSet 使用的就是組合 HashMap，其優(yōu)點如下：

繼承表示父子類是同一個事物，而 Set 和 Map 本來就是想表達兩種事物，所以繼承不妥，而且 Java 語法限制，子類只能繼承一個父類，后續(xù)難以擴展。

組合更加靈活，可以任意的組合現(xiàn)有的基礎類，并且可以在基礎類方法的基礎上進行擴展、編排等，而且方法命名可以任意命名，無需和基礎類的方法名稱保持一致。

組合就是把 HashMap 當作自己的一個局部變量，以下是 HashSet 的組合實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. // 把 HashMap 組合進來，key 是 Hashset 的 key，value 是下面的 PRESENT 
    2. 
  
  
  
  
  2. private transient HashMap map; 
    3. 
  
  
  
  
  3. // HashMap 中的 value 
    4. 
  
  
  
  
  4. private static final Object PRESENT = new Object(); 
    5.

從這兩行代碼中，我們可以看出兩點：

我們在使用 HashSet 時，比如 add 方法，只有一個入?yún)?，但組合的 Map 的 add 方法卻有 key，value 兩個入?yún)?，相對應?Map 的 key 就是我們 add 的入?yún)ⅲ瑅alue 就是第二行代碼中的 PRESENT，此處設計非常巧妙，用一個默認值 PRESENT 來代替 Map 的 Value;

我們再來看看add方法：

 
 
 
 
    
  
  
  
  
  1. public boolean add(E e) { 
    2. 
  
  
  
  
  2.     // 直接使用 HashMap 的 put 方法，進行一些簡單的邏輯判斷 
    3. 
  
  
  
  
  3.     return map.put(e, PRESENT)==null; 
    4. 
  
  
  
  
  4. } 
    5.

我們進入更底層源碼java.util.HashMap#put:

 
 
 
 
    
  
  
  
  
  1. public V put(K key, V value) {  
    2. 
  
  
  
  
  2.  return putVal(hash(key), key, value, false, true);  
    3. 
  
  
  
  
  3. } 
    4.

再瞧瞧hash方法：

 
 
 
 
    
  
  
  
  
  1. static final int hash(Object key) {  
    2. 
  
  
  
  
  2.  int h;  
    3. 
  
  
  
  
  3.  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
    4. 
  
  
  
  
  4. } 
    5.

可以看到如果 key 為 null ，哈希值為 0，否則將 key 通過自身hashCode函數(shù)計算的的哈希值和其右移 16 位進行異或運算得到最終的哈希值。

我們再回到 java.util.HashMap#putVal中：

在 java.util.HashMap#putVal中，直接通過 (n - 1) & hash 來得到當前元素在節(jié)點數(shù)組中的位 置。如果不存在，直接構(gòu)造新節(jié)點并存儲到該節(jié)點數(shù)組的對應位置。如果存在，則通過下面邏 輯：

 
 
 
 
    
  
  
  
  
  1. p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) 
    2.

來判斷元素是否相等。

如果相等則用新值替換舊值，否則添加紅黑樹節(jié)點或者鏈表節(jié)點。

總結(jié)：通過HashMap的key的唯一性來保證的HashSet元素的唯一性。

最后再看看：

《阿里巴巴Java開發(fā)手冊》里面還有這樣一段描述：

到現(xiàn)在是不是明白了，這個2，3點的原因

性能對比

其實HashSet和ArrayList去重性能差異的核心在于contains函數(shù)性能對比。

我們分別查看java.util.HashSet#contains和java.util.ArrayList#contains的實現(xiàn)。

java.util.HashSet#contains源碼：

 
 
 
 
    
  
  
  
  
  1. public boolean contains(Object o) { 
    2. 
  
  
  
  
  2.         return map.containsKey(o); 
    3. 
  
  
  
  
  3.     } 
    4.

最終也是通過HashMap判斷的

如果 hash 沖突不是極其嚴重(大多數(shù)都沒怎么有哈希沖突)，n 個元素依次判斷并插入到 Set 的時間復雜度接近于 O (n)，查找的復雜度是O(1)。

接下來我們看java.util.ArrayList#contains的源碼：

 
 
 
 
    
  
  
  
  
  1. public boolean contains(Object o) { 
    2. 
  
  
  
  
  2.         return indexOf(o) >= 0; 
    3. 
  
  
  
  
  3.     } 
    4. 
 
 
 
 
 
 
 
 
    
  
  
  
  
  1. public int indexOf(Object o) { 
    2. 
  
  
  
  
  2.         if (o == null) { 
    3. 
  
  
  
  
  3.             for (int i = 0; i < size; i++) 
    4. 
  
  
  
  
  4.                 if (elementData[i]==null) 
    5. 
  
  
  
  
  5.                     return i; 
    6. 
  
  
  
  
  6.         } else { 
    7. 
  
  
  
  
  7.             for (int i = 0; i < size; i++) 
    8. 
  
  
  
  
  8.                 if (o.equals(elementData[i])) 
    9. 
  
  
  
  
  9.                     return i; 
    10. 
  
  
  
  
  10.         } 
    11. 
  
  
  
  
  11.         return -1; 
    12. 
  
  
  
  
  12.     } 
    13.

發(fā)現(xiàn)其核心邏輯為：如果為 null, 則遍歷整個集合判斷是否有 null 元素;否則遍歷整個列表，通 過 o.equals(當前遍歷到的元素) 判斷與當前元素是否相等，相等則返回當前循環(huán)的索引。

所以， java.util.ArrayList#contains判斷并插入n個元素到 Set 的時間復雜度接近于O (n^2)，查找的復雜度是O(n)。

因此，通過時間復雜度的比較，性能差距就不言而喻了。

我們分別將兩個時間復雜度函數(shù)進行作圖， 兩者增速對比非常明顯：

如果數(shù)據(jù)量不大時采用 List 去重勉強可以接受，但是數(shù)據(jù)量增大后，接口響應時間會超慢，這 是難以忍受的，甚至造成大量線程阻塞引發(fā)故障。

本文轉(zhuǎn)載自微信公眾號「 月伴飛魚」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 月伴飛魚公眾號。


當前文章：記一次集合去重導致的線上問題
文章來源：http://www.dlmjj.cn/article/dhdgpeg.html