并查集是一種常用的數(shù)據(jù)結(jié)構(gòu)，用于多個(gè)集合元素的合并問(wèn)題。實(shí)際應(yīng)用場(chǎng)景下，并查集簡(jiǎn)直是必不可缺的工具，例如：

（1）查找二值化圖像的連通區(qū)域，連通的區(qū)域?yàn)橐粋€(gè)獨(dú)立集合，一張圖中可能有多個(gè)連通區(qū)域。

（2）判斷當(dāng)前路徑結(jié)構(gòu)中是否存在環(huán)路，連通的邊都屬于同一個(gè)集合，有環(huán)的圖中，則存在節(jié)點(diǎn)的度>=2，若進(jìn)行并查集合并操作，必然有節(jié)點(diǎn)被重復(fù)合并，若出現(xiàn)重復(fù)合并的情況，就說(shuō)明圖中有環(huán)。

（3）簡(jiǎn)單的歸類(lèi)問(wèn)題，例如內(nèi)存池中，一個(gè)對(duì)象的存儲(chǔ)空間是由多個(gè)碎片內(nèi)存構(gòu)成的，那么就需要使用并查集將這些內(nèi)存地址合并為一個(gè)集合，該集合的根節(jié)點(diǎn)為這個(gè)對(duì)象內(nèi)存的首地址。多個(gè)集合分別對(duì)應(yīng)多個(gè)不同的對(duì)象存儲(chǔ)空間。

一般的并查集實(shí)現(xiàn)

傳統(tǒng)的并查集是基于樹(shù)形結(jié)構(gòu)實(shí)現(xiàn)的，屬于同一集合的元素?fù)碛邢嗤母?jié)點(diǎn)，在實(shí)現(xiàn)兩個(gè)集合合并時(shí)，需要分別找到兩個(gè)集合的根節(jié)點(diǎn)，然后再連接根節(jié)點(diǎn)生成新的樹(shù)。而查找元素屬于哪個(gè)集合時(shí)，則需要從當(dāng)前元素開(kāi)始一級(jí)級(jí)向上，直到查找到根節(jié)點(diǎn)為止。

擁有相同根節(jié)點(diǎn)的元素屬于同一個(gè)集合，反之它們屬于不同集合。

以下代碼是百度AI文心一言自動(dòng)生成的，經(jīng)過(guò)測(cè)試無(wú)誤：

運(yùn)行效率分析

1. 時(shí)間復(fù)雜度：olog(n)

上面的并查集代碼中，是基于樹(shù)形結(jié)構(gòu)進(jìn)行存儲(chǔ)的，且進(jìn)行了路徑壓縮。而每次的合并操作，都需要找到根節(jié)點(diǎn)。假設(shè)輸入節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則一級(jí)級(jí)向上找到根節(jié)點(diǎn)需要log(n)次。

2. 空間復(fù)雜度：o(2*n)

顯然，在代碼中創(chuàng)建了兩個(gè)數(shù)組，一個(gè)存儲(chǔ)節(jié)點(diǎn)的父節(jié)點(diǎn)，一個(gè)存儲(chǔ)節(jié)點(diǎn)的秩。當(dāng)你有1920*1080個(gè)節(jié)點(diǎn)需要進(jìn)行合并時(shí)，并查集數(shù)組就要占用4147200 * sizeof(int)字節(jié)的空間，相當(dāng)于15MB的內(nèi)存。

我滴媽！在并查集初始階段就要?jiǎng)?chuàng)建這么大的數(shù)組，而實(shí)際情況下合并后的集合一般就只有幾十個(gè)，實(shí)屬浪費(fèi)內(nèi)存。若采用動(dòng)態(tài)分配的方式，可以將已合并節(jié)點(diǎn)內(nèi)存釋放(失去引用GC自動(dòng)回收)掉。

缺點(diǎn)：

（1）查詢是基于順序查詢，速度慢。

（2）占用空間過(guò)大，初始階段就分配了所有內(nèi)存，沒(méi)有做到按需分配。

（3）代碼太長(zhǎng)了，完全重復(fù)造輪子，沒(méi)有用到Java自帶的一些數(shù)據(jù)結(jié)構(gòu)。

基于哈希表的并查集實(shí)現(xiàn)

下面我將一一解決上面三個(gè)問(wèn)題，并引出基于哈希表的并查集實(shí)現(xiàn)思路。

（1）查詢速度

由于順序查詢的速度過(guò)于緩慢，當(dāng)節(jié)點(diǎn)數(shù)量很大時(shí)，順序查詢的劣勢(shì)就會(huì)十分明顯。因此，可以采用散列表結(jié)構(gòu)進(jìn)行存儲(chǔ)。眾所周知，散列表的查詢速度是o(1)，在根據(jù)當(dāng)前節(jié)點(diǎn)查詢其根節(jié)點(diǎn)時(shí)，一瞬間就能查詢到。

而且Java提供了HashMap數(shù)據(jù)結(jié)構(gòu)，支持鍵值對(duì)形式的散列表存儲(chǔ)。

存儲(chǔ)結(jié)構(gòu):

KEY????： 存儲(chǔ)當(dāng)前集合的根節(jié)點(diǎn)

VALUE：存儲(chǔ)當(dāng)前集合

舉個(gè)例子：

這是一張3 * 3大小的二值化圖像，將圖中的連通的節(jié)點(diǎn)作為一個(gè)獨(dú)立集合。

HashMap 中的值如下：

{1 : {1 , 2 , 3}}

{4 : {4 , 5 , 6}}?

表示，以1為根節(jié)點(diǎn)的集合為{1 , 2 , 3}。以4為根節(jié)點(diǎn)的集合為{4 , 5 , 6}。

在Java中HashMap的結(jié)構(gòu)為：

Key是Integer類(lèi)型，表示根節(jié)點(diǎn)。

Value是HashSet<Object>類(lèi)型，用于存儲(chǔ)集合內(nèi)容。

（2）占用空間

由于Java的HashMap可以通過(guò)put函數(shù)動(dòng)態(tài)添加表項(xiàng)，所以這種并查集可以在有需要時(shí)動(dòng)態(tài)創(chuàng)建新的集合，并將新創(chuàng)建的集合存儲(chǔ)到HashMap中。

同樣的，在并查集合并操作時(shí)，HashMap中原來(lái)的集合會(huì)跟另一個(gè)集合合并，而原來(lái)的集合將會(huì)失去引用，被GC回收。

因此，在空間占用上，散列表并查集具有良好的動(dòng)態(tài)內(nèi)存性能，不會(huì)在一瞬間申請(qǐng)過(guò)多的內(nèi)存，也不會(huì)浪費(fèi)存儲(chǔ)空間。

合并操作:

將根節(jié)點(diǎn)為1的集合{1,2,3}與根節(jié)點(diǎn)為4的集合{4,5,6}進(jìn)行合并。

HashMap中的值如下：

{1 : {1 , 2 , 3}}

{4 : {4 , 5 , 6}}?

第一步：

將根節(jié)點(diǎn)為4的集合元素{4 , 5 , 6}賦值到根節(jié)點(diǎn)為1的集合中。結(jié)果如下：

{1 : {1 , 2 , 3 , 4 , 5 , 6}}

{4 : {4 , 5 , 6}}

第二步：

將根節(jié)點(diǎn)為4的集合指向根節(jié)點(diǎn)為1的集合，此時(shí){4,5,6}集合就失去引用了。結(jié)果如下：

{1 : {1 , 2 , 3 , 4 , 5 , 6}}

{4 : {1 , 2 , 3 , 4 , 5 , 6}}

節(jié)點(diǎn)1和節(jié)點(diǎn)4都指向了同一個(gè)集合{1 , 2 , 3 , 4 , 5 , 6}

之后如果有其他節(jié)點(diǎn)和節(jié)點(diǎn)4合并，則實(shí)際上是那個(gè)節(jié)點(diǎn)的集合和節(jié)點(diǎn)1的集合進(jìn)行合并。然后再將自己的集合指向節(jié)點(diǎn)1的集合。

（3）代碼長(zhǎng)度

廢話不多說(shuō)，直接看代碼實(shí)現(xiàn)：

肉眼可見(jiàn)，函數(shù)里的代碼量少到可憐，因?yàn)楹侠磉\(yùn)用了Java封裝好的數(shù)據(jù)結(jié)構(gòu)。

應(yīng)用實(shí)例

作為例子，下面我將使用散列表并查集實(shí)現(xiàn)八方向二值化圖像連通域查詢算法，并對(duì)兩種并查集的實(shí)際運(yùn)行性能進(jìn)行分析：

輸入圖片:

運(yùn)行結(jié)果：

圖中黃色部分是相同的集合，并不占用額外內(nèi)存空間。

運(yùn)行時(shí)間：

這張圖的大小是450*681，運(yùn)行完連通節(jié)點(diǎn)合并花費(fèi)64毫秒。