哈希冲突处理对比：拉链法 vs 开放寻址法

📖 算法原理：当哈希发生碰撞碰撞时的消解之道

哈希冲突（Collision）是指不同的键值 $key_1 \neq key_2$ 通过散列函数计算后落在了相同的哈希槽内，即 $H(key_1) == H(key_2)$。因为哈希映射是空间压缩的，冲突在所难免。

📐 两种主流的冲突消解方法理论对比

拉链法（Chaining，链地址法）：
- 存储结构：哈希表的每个槽位是一个链表的头指针。所有发生冲突的元素直接挂接在该槽位对应的单链表末尾。
- 优缺点：不会发生空间蔓延拥堵，装载因子（Load Factor）可以大于 1。但需要额外的单链表指针内存开销，链表节点物理内存不连续，对 Cache 缓存不友好。
开放寻址法 (Open Addressing - 线性探测)：
- 存储结构：所有数据都保存在哈希表数组本身。当 $H(key)$ 被占用时，顺延向右依次探测下一个空位：$H_i = (H(key) + i) \bmod M$。
- 优缺点：没有指针开销，缓存连续性极佳。但在高装载因子下极易出现“主聚集”现象，探测次数随之暴增，装载因子必须严格限制在 $0.7 \sim 0.8$ 以下。

输入 Key (建议多次输入 7 的倍数造成冲突)：

输入数值并点击"对比插入"，观摩两侧哈希表的解决冲突状态机。

🔗 1. 拉链法哈希链表 (Chaining Method Array - M = 7)

🔎 2. 开放寻址线性探测表 (Open Addressing Probing Array - M = 7)

// 拉链法链表结构
vector<int> head[M]; 

void insertChaining(int key) {
    int idx = key % M;
    // 发生冲突时，直接压入对应桶的单链表尾部
    head[idx].push_back(key); 
}

// 开放寻址线性探测结构
int table[M];
bool occupied[M];

void insertProbing(int key) {
    int idx = key % M;
    // 当该槽位被占用，循环向右探测下一个槽位
    while (occupied[idx]) {
        idx = (idx + 1) % M; // 线性探测
    }
    table[idx] = key;
    occupied[idx] = true;
}

📋 冲突对比步骤日志