Java集合去重導(dǎo)致的線上問題

更新時(shí)間：2022年04月21日 14:00:58 作者：程序員段飛?

這篇文章主要介紹了Java集合去重導(dǎo)致的線上問題，根據(jù)主題提出Set是怎樣保證數(shù)據(jù)的唯一性的，為什么兩種去重方式性能差距這么大的問題，下文解決思路需要的小伙伴可以參考一下

前言：

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

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

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

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

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

HashSet源碼

先看看類注釋：

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

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

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

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

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

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

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

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

// 把 HashMap 組合進(jìn)來，key 是 Hashset 的 key，value 是下面的 PRESENT
private transient HashMap<E,Object> map;
// HashMap 中的 value
private static final Object PRESENT = new Object();

從這兩行代碼中，我們可以看出兩點(diǎn)：

我們?cè)谑褂?HashSet 時(shí)，比如 add 方法，只有一個(gè)入?yún)?，但組合的 Map 的 add 方法卻有 key，value 兩個(gè)入?yún)?，相?duì)應(yīng)上 Map 的 key 就是我們 add 的入?yún)ⅲ瑅alue 就是第二行代碼中的 PRESENT，此處設(shè)計(jì)非常巧妙，用一個(gè)默認(rèn)值 PRESENT 來代替 Map 的 Value；

我們?cè)賮砜纯碼dd方法：

public boolean add(E e) {
    // 直接使用 HashMap 的 put 方法，進(jìn)行一些簡(jiǎn)單的邏輯判斷
    return map.put(e, PRESENT)==null;
}

我們進(jìn)入更底層源碼java.util.HashMap#put:

public V put(K key, V value) { 
 return putVal(hash(key), key, value, false, true); 
}

再瞧瞧hash方法：

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

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

我們?cè)倩氐?nbsp;java.util.HashMap#putVal中：

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

p.hash == hash &amp;&amp; ((k = p.key) == key || (key != null &amp;&amp; key.equals(k)))
復(fù)制代碼

來判斷元素是否相等。

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

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

最后再看看：

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

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

性能對(duì)比

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

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

java.util.HashSet#contains源碼：

public boolean contains(Object o) {
        return map.containsKey(o);
    }

最終也是通過HashMap判斷的

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

接下來我們看java.util.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;
    }--pre>

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

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

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

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