系列文章目录：

并查集

并查集（Disjoint Set Union, Union-Find）是一种高效维护多个不相交集合的数据结构。它用一个森林（Forest）实现：每个集合（集合间不相交）对应一棵树，树的根（root）作为该集合的“代表”或“标识”。

主要操作有两类：

查找Find(x)：查找元素所在的集合，即找到它的根。
合并Union(x, y)：将两个集合合并为一个集合，即找到两个根，将一个根的父节点指向另一个根。

用途包括判断两个元素是否属于同一个集合、合并集合、判环（比如在 Kruskal 算法里避免生成环），等等。

基本实现

由于是基于森林的写法，我们这里用父节点表示法来表示树，以及再开一个root[]来记录根节点的位置。

初始化

我们把每个节点都看作一个集合，初始化时每个节点的父节点都指向自己，表示每个节点都是根节点。

1	parent[i] = i;

查找

我们需要沿着树向上移动，直至找到根节点。

int find(int x)
{
    while(x!=parent[x]) x=parent[x];
    return x;
}

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

void unite(int a, int b)
{
    int ra=find(a), rb=find(b);
    if (ra!=rb) parent[ra]=rb;  
}

优化

路径压缩（Path Compression）

经典的find会让树变得很深，效率下降。路径压缩优化的步骤是：每次find(x)时，都让访问路径上的节点直接挂到根上，极大降低树的高度：

int find(int x)
{
    if(parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

这样平均下来每次操作几乎就是常数时间（用的是反阿克曼函数 α(n) 量级）

按秩合并（Union by Rank/Size）

当合并两个集合（树）时，我们可以让秩（rank,size）小的树挂在秩大的树下面，这样能防止树高过快增长：

秩通常代表树的高度估计值
合并后仅在秩相等时，新的根秩加一

int rank[N];
void unite(int a, int b)
{
    int ra=find(a), rb=find(b);
    if(ra != rb)
    {
        if (rank[ra] < rank[rb]) parent[ra]=rb;
        else if (rank[ra] > rank[rb]) parent[rb]=ra;
        else
        {
            parent[rb] = ra;
            rank[ra]++;
        }
    }
}

应用

对于连通性问题，可以用并查集维护连通性，判断两个节点是否连通，或者合并两个连通区域。
对于图论中的最小生成树问题，可以用并查集维护连通性，避免生成环。

哈希表

哈希表（Hash Table），又叫散列表，是一种基于键Key直接访问值Value的数据结构。它的思想是：通过哈希函数（Hash Function），把键映射到一个数组下标，从而实现 O(1) 时间复杂度的查找和存取。

可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。

对于C++中直接能够使用的哈希表是unordered_map

cppreference-unordered_map。

以上即哈希表的一个简单例子，其中b[1012]到b[1016]是哈希表的各个桶，每个桶里存放的元素存在哈希冲突（即哈希函数计算出的下标相同），这个问题在哈希函数中会讲到。

哈希函数

$key=H(value)$

要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。举个例子，如果键值是一个人的身份证号码，哈希函数就可以是号码的后四位，当然也可以是号码的前四位。生活中常用的「手机尾号」也是一种哈希函数。在实际的应用中，键值可能是更复杂的东西，比如浮点数、字符串、结构体等，这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。

常见的hash值设计方法有：

除法散列法：
$key\ = \ value \ (\mathbf{mod} \ M)$ 其中 $M$ 是一个素数或者 $2^p-1$
乘法散列法：
$key\ = \ \left \lfloor M \cdot (A \cdot key \ (\mathbf {mod} \ 1)) \right \rfloor $
其中 $0<A<1$ 并且最好接近黄金比例 $\frac{\sqrt{5}-1}{2} \approx 0.618$ ，并且这里的 $(\mathbf {mod} \ 1)$ 表示取(double)(A*key)的小数部分
字符串hash：
$key = (\sum_{i=0}^{n-1} s[i] \cdot p^i) \ \mathbf {mod} \ M$
这里的p是常数，M是素数，s是字符串（字符按照ASCII码来计算），n是字符串长度
CRC/位运算哈希：
h = (h << 5) ^ (h >> 27) ^ key
这里使用的是迭代的方式 $h_{i+1}=H(h_i, key_i)$

好哈希函数的标准：简单快速、分布均匀、冲突尽可能少

这里有个小技巧，把计算出的值（取模之前），都作为unsigned long long这样超过 $2^{64}$ 后的数会自然溢出，等价于取模操作了。可以使操作更加方便。

哈希冲突

哈希函数计算出来的索引可能相同，这就是哈希冲突。哈希冲突的解决方法有：

开放定址法（Open Addressing）
如果位置被占用那么寻找下一个空位
- 线性探测： $H_i = ( H(key) + d_i) \ (\mathbf {mod} \ M)$，$d_i = 0,1,2,3,…,M-1$
- 二次探测： $H_i = ( H(key) + d_i) \ (\mathbf {mod} \ M)$，$d_i = 0,1^2,-1^2,2^2,-2^2,…,k^2,-k^2$，$k < \sqrt{M}$
- 双重散列： $H_i = ( H_1(key) + i \cdot H_2(value) ) \ (\mathbf {mod} \ M)$，$H_1$和$H_2$是两个不同的哈希函数

链地址法（Chaining）
每个位置存储一个链表或者vector，冲突的元素直接加到链表上，前面的图例就是链地址法。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 $1\ldots M$ ，哈希表的大小为 $N$ ，那么一次插入/查询需要进行期望 $O(\frac{N}{M})$ 次比较。
这里提供一个io wiki上一个不错的代码

struct hash_map {  // 哈希表模板

  struct data {
    long long u;
    int v, nex;
  };  // 前向星结构

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  // 这里使用 (u % SZ + SZ) % SZ 而非 u % SZ 的原因是
  // C++ 中的 % 运算无法将负数转为正数

  int& operator[](long long u) {
    int hu = hash(u);  // 获取头指针
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = data{u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

代码实现

struct HashTable {
    static const int M = 1009; 
    vector<pair<int,int>> table[M];

    int hashFunc(int key) {
        return key % M;
    }

    void insert(int key, int value) {
        int h = hashFunc(key);
        for (auto &p : table[h]) {
            if (p.first == key) { p.second = value; return; }
        }
        table[h].push_back({key, value});
    }

    int find(int key) {
        int h = hashFunc(key);
        for (auto &p : table[h]) {
            if (p.first == key) return p.second;
        }
        return -1; // not found
    }
};

字符串哈希

字符串的哈希函数设计可以参考上面的字符串hash公式，以及oi wiki 上已经解释地很清楚了，这里给出c++的模板实现：

模数 Hash：

using std::string;

constexpr int M = 1e9 + 7;
constexpr int B = 233;

using ll = long long;

int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = ((ll)res * B + s[i]) % M;
  }
  return res;
}

bool cmp(const string& s, const string& t) {
  return get_hash(s) == get_hash(t);
}

双值 Hash：

using ull = unsigned long long;
ull base = 131;
ull mod1 = 212370440130137957, mod2 = 1e9 + 7;

ull get_hash1(std::string s) {
  int len = s.size();
  ull ans = 0;
  for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod1;
  return ans;
}

ull get_hash2(std::string s) {
  int len = s.size();
  ull ans = 0;
  for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod2;
  return ans;
}

bool cmp(const std::string s, const std::string t) {
  bool f1 = get_hash1(s) != get_hash1(t);
  bool f2 = get_hash2(s) != get_hash2(t);
  return f1 || f2;
}

个人偏好（用于子字符串的匹配）

struct StringHash
{
    using ull = unsigned long long;
    static const ull base = 131;
    vector<ull> h, p;             // h 前缀哈希, p 幂次表
    
    StringHash(const string &s)
    {
        int n = s.size();
        h.assign(n + 1, 0);
        p.assign(n + 1, 1);
        for (int i = 1; i <= n; i++)
        {
            h[i] = h[i-1] * base + (s[i-1] - 'a' + 1);
            p[i] = p[i-1] * base;
        }
    }
    
    // 查询子串 [l,r] 的哈希 (1-indexed)
    ull get(int l, int r)
    {
        return h[r] - h[l-1] * p[r-l+1];
    }
};

具体使用

判断两个字符串是否相等
if(!cmp(s,t))cout << "No";
判断字字串符串是否相等

这里先预处理字符串的hash前缀 $H[i+1]=(H[i]\cdot base+s[i]) \ (\mathbf{mod} \ M)$
然后再计算子串s[l,l+1,,,r-1,r]的hash，并对比 $hash(l,r)=(H[r]-H[l-1]\cdot base^{r-l+1})\ (\mathbf{mod} \ M)$

这里取单模哈希的方法做例子：

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
const ull base = 131;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    int n=s.size(), m=t.size();
    vector<ull> hp(n+1, 0), pb(n+1, 1);
    for(int i=1; i<=n; i++)
    {
        hp[i]=hp[i-1]*base + (s[i - 1] - 'a' + 1);
        pb[i]=pb[i-1]*base;  //同时计算base的幂
    }

    // 计算模式串哈希
    ull ht = 0;
    for (int i=0; i<m; i++)
        ht=ht*base+(t[i]-'a'+1);

    // 枚举所有长度 m 的子串哈希比较
    int cnt=0;
    for(int i=0; i+m<=n; i++)
    {
        ull sub=hp[i+m]-hp[i]*pb[m];
        if(sub==ht) cnt++;
    }

    cout << cnt << "\n";
    return 0;
}

最长公共前缀 / 最长重复子串

二分+双hash
1. 二分长度L
2. 枚举长度为L的子串，存哈希值
3. 果存在重复 → 增大 L，否则减小 L

回文或反向匹配
遍历两边，计算字符串的正反hash，然后判断是否相等

注意：

只需要模式串匹配：用KMP更稳定，无冲突风险。
需要频繁子串比较 / 多次查询：用哈希更方便，尤其是在线性区间查询时几乎必选。

堆

堆就是一颗树，树上的节点都有各自的键值（key），且每个节点的key都大于或等于其子节点的key（大根堆），或者小于或等于其子节点的key（小根堆）。

在C++ STL中priority_queue就是堆的一种实现，默认为大根堆。

堆的主要操作有：

建堆(Build Heap):
- 从一个无序数组构建一个堆 $O(n)$
插入(Insert/Push):
- 把新元素插入到堆的末尾，然后上浮(Sift Up) $O(\log n)$
取堆顶(Get Top/Peek):
- 直接返回堆顶元素 $O(1)$
删除(Delete/Pop):
- 把堆顶元素删除，然后把堆的最后一个元素放到堆顶，然后下沉(Sift Down) $O(\log n)$
调整(Adjust/Heapify):
- 调整某个节点以下的子树，使其满足堆性质 $O(\log n)$
合并(Merge/Meld):
- 合并两个堆，斐波那契堆可以达到 $O(1)$

二叉堆（Binary Heap）

二叉堆就是一棵完全二叉树，且满足堆性质。

这里以大根堆即父节点的权值大于等于子节点的权值为例。

存储方式：数组，从1开始存储。

根节点a[1]
对于某个节点a[i]
- 左子节点为a[2i]
- 右子节点为a[2i+1]
- 父节点为a[i/2]

这些性质在讲二叉树时强调过。

过程

插入（Insert/Push）

把新元素放到数组末尾（堆的最后一个位置）
然后不断与其父节点比较，如果比父节点大，则交换位置，直到比父节点小或到达根节点（满足堆的性质），这个过程称为上浮（Sift Up）
时间复杂度：$O(\log n)$

void push(vector<int> &heap,int x)
{
    heap.push_back(x);
    int i=heap.size()-1;
    while(i>1&&heap[i]>heap[i/2])
    {
        swap(heap[i],heap[i/2]);
        i/=2;
    }
}

删除（Delete/Pop）

如果直接从欲删除的点断开，则会多出一颗树，我们可以按照以下步骤来删除堆顶元素：

取出堆顶元素，把堆的最后一个元素放到堆顶
从根开始，不断和其子节点比较，如果比子节点小，则交换位置，直到比子节点大或到达叶子节点（满足堆的性质），这个过程称为下沉（Sift Down）
时间复杂度：$O(\log n)$

void pop(vector<int> &heap)
{
    int n = heap.size();
    heap[1] = heap[(int)heap.size() - 1];
    heap.pop_back();
    int i = 1;
    while (1)
    {
        int lag = i;
        int l=i*2, r=i*2+1;
        // 找到最大的子节点
        if(l < n && heap[l] > heap[lag]) lag = l;
        if(r < n && heap[r] > heap[lag]) lag = r;
        if(lag == i) break;
        // 把最大的子节点放到父节点
        swap(heap[i], heap[lag]);
        i = lag;
    }
}

建堆（Build Heap）

假设我们有一个无序数组，如何把它变成一个堆呢？下面有两种方式：

利用刚刚写的push操作，一个一个插入，时间复杂度是$O(n\log n)$
从最后一个非叶子节点开始下沉，时间复杂度是$O(n)$

这里以第二种方式为例：

void buildHeap(vector<int> &heap)
{
    for(int i=heap.size()/2; i>=1; i--)
    {
        int j=i;
        while(1)
        {
            int lag=j;
            int l=j*2, r=j*2+1;
            if(l < heap.size() && heap[l] > heap[lag]) lag = l;
            if(r < heap.size() && heap[r] > heap[lag]) lag = r;
            if(lag == j) break;
            swap(heap[j], heap[lag]);
            j = lag;
        }
    }
}

完整的代码（大根堆）

struct BinaryHeap
{
    vector<int> heap;

    void push(int x)
    {
        heap.push_back(x);
        int i=heap.size()-1;
        while(i>1&&heap[i]>heap[i/2])
        {
            swap(heap[i],heap[i/2]);
            i/=2;
        }
    }

    void pop()
    {
        int n=heap.size();
        heap[1]=heap[n-1];
        heap.pop_back();
        int i=1;
        while(1)
        {
            int largest=i;
            int l=i*2, r=i*2+1;
            if(l<n && heap[l]>heap[largest]) largest=l;
            if(r<n && heap[r]>heap[largest]) largest=r;
            if(largest==i) break;
            swap(heap[i],heap[largest]);
            i=largest;
        }
    }

    int top()
    {
        return heap[1];
    }

    void buildHeap(vector<int> &arr)
    {
        for(int i=arr.size()/2; i>=1; i--)
        {
            int j=i; 
            while(1)
            {
                int largest=j;
                int l=j*2, r=j*2+1;
                if(l<arr.size() && arr[l]>arr[largest]) largest=l;
                if(r<arr.size() && arr[r]>arr[largest]) largest=r;
                if(largest==j) break;
                swap(arr[j],arr[largest]);
                j=largest;
            }
        }
    }
}
/*
用法：
BinaryHeap heap;
heap.push(1);
heap.push(2);
heap.push(3);
heap.pop();
cout << heap.top() << "\n";
vector<int> arr={3,212,33,44,15};
BinaryHeap heapp;
heapp.buildHeap(arr);
*/

配对堆（Pairing Heap）

配对堆本质是一种可并堆（Meldable Heap），比二叉堆更适合频繁的合并merge操作，常用于优先队列的实现。支持插入，查询/删除堆顶，合并等操作。有速度快和结构简单的优势，但由于其为基于势能分析的均摊复杂度，无法可持久化。

由于配对堆使用的是一颗多叉树，每个节点的权值都

数据结构笔记--并查集哈希表堆

并查集