并查集是一种常用的数据结构，用于多个集合元素的合并问题。实际应用场景下，并查集简直是必不可缺的工具，例如：

（1）查找二值化图像的连通区域，连通的区域为一个独立集合，一张图中可能有多个连通区域。

（2）判断当前路径结构中是否存在环路，连通的边都属于同一个集合，有环的图中，则存在节点的度>=2，若进行并查集合并操作，必然有节点被重复合并，若出现重复合并的情况，就说明图中有环。

（3）简单的归类问题，例如内存池中，一个对象的存储空间是由多个碎片内存构成的，那么就需要使用并查集将这些内存地址合并为一个集合，该集合的根节点为这个对象内存的首地址。多个集合分别对应多个不同的对象存储空间。

一般的并查集实现

传统的并查集是基于树形结构实现的，属于同一集合的元素拥有相同的根节点，在实现两个集合合并时，需要分别找到两个集合的根节点，然后再连接根节点生成新的树。而查找元素属于哪个集合时，则需要从当前元素开始一级级向上，直到查找到根节点为止。

拥有相同根节点的元素属于同一个集合，反之它们属于不同集合。

以下代码是百度AI文心一言自动生成的，经过测试无误：

运行效率分析

1. 时间复杂度：olog(n)

上面的并查集代码中，是基于树形结构进行存储的，且进行了路径压缩。而每次的合并操作，都需要找到根节点。假设输入节点为叶子节点，则一级级向上找到根节点需要log(n)次。

2. 空间复杂度：o(2*n)

显然，在代码中创建了两个数组，一个存储节点的父节点，一个存储节点的秩。当你有1920*1080个节点需要进行合并时，并查集数组就要占用4147200 * sizeof(int)字节的空间，相当于15MB的内存。

我滴妈！在并查集初始阶段就要创建这么大的数组，而实际情况下合并后的集合一般就只有几十个，实属浪费内存。若采用动态分配的方式，可以将已合并节点内存释放(失去引用GC自动回收)掉。

缺点：

（1）查询是基于顺序查询，速度慢。

（2）占用空间过大，初始阶段就分配了所有内存，没有做到按需分配。

（3）代码太长了，完全重复造轮子，没有用到Java自带的一些数据结构。

基于哈希表的并查集实现

下面我将一一解决上面三个问题，并引出基于哈希表的并查集实现思路。

（1）查询速度

由于顺序查询的速度过于缓慢，当节点数量很大时，顺序查询的劣势就会十分明显。因此，可以采用散列表结构进行存储。众所周知，散列表的查询速度是o(1)，在根据当前节点查询其根节点时，一瞬间就能查询到。

而且Java提供了HashMap数据结构，支持键值对形式的散列表存储。

存储结构:

KEY    ： 存储当前集合的根节点

VALUE：存储当前集合

举个例子：

这是一张3 * 3大小的二值化图像，将图中的连通的节点作为一个独立集合。

HashMap 中的值如下：

{1 : {1 , 2 , 3}}

{4 : {4 , 5 , 6}} 

表示，以1为根节点的集合为{1 , 2 , 3}。以4为根节点的集合为{4 , 5 , 6}。

在Java中HashMap的结构为：

Key是Integer类型，表示根节点。

Value是HashSet<Object>类型，用于存储集合内容。

（2）占用空间

由于Java的HashMap可以通过put函数动态添加表项，所以这种并查集可以在有需要时动态创建新的集合，并将新创建的集合存储到HashMap中。

同样的，在并查集合并操作时，HashMap中原来的集合会跟另一个集合合并，而原来的集合将会失去引用，被GC回收。

因此，在空间占用上，散列表并查集具有良好的动态内存性能，不会在一瞬间申请过多的内存，也不会浪费存储空间。

合并操作:

将根节点为1的集合{1,2,3}与根节点为4的集合{4,5,6}进行合并。

HashMap中的值如下：

{1 : {1 , 2 , 3}}

{4 : {4 , 5 , 6}} 

第一步：

将根节点为4的集合元素{4 , 5 , 6}赋值到根节点为1的集合中。结果如下：

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

{4 : {4 , 5 , 6}}

第二步：

将根节点为4的集合指向根节点为1的集合，此时{4,5,6}集合就失去引用了。结果如下：

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

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

节点1和节点4都指向了同一个集合{1 , 2 , 3 , 4 , 5 , 6}

之后如果有其他节点和节点4合并，则实际上是那个节点的集合和节点1的集合进行合并。然后再将自己的集合指向节点1的集合。

（3）代码长度

废话不多说，直接看代码实现：

肉眼可见，函数里的代码量少到可怜，因为合理运用了Java封装好的数据结构。

应用实例

作为例子，下面我将使用散列表并查集实现八方向二值化图像连通域查询算法，并对两种并查集的实际运行性能进行分析：

输入图片:

运行结果：

图中黄色部分是相同的集合，并不占用额外内存空间。

运行时间：

这张图的大小是450*681，运行完连通节点合并花费64毫秒。