哈希冲突 与 STL 里hashtable的实现 哈希桶vector＜Node*＞ bucket + 链表实现，每次冲突更改对应bucket的链表头节点

📌 哈希冲突（Hash Collision）定义

哈希冲突（Hash Collision） 发生在 不同的键（Key）通过哈希函数映射到相同的哈希值（索引） 的情况。

📌 1. 为什么会发生哈希冲突？

哈希冲突是不可避免的，主要原因有：

1. 有限的桶数量：哈希表的**桶（bucket）**数量通常比所有可能的键空间要小。
2. 哈希函数的碰撞：哈希函数不能保证唯一性，不同的输入可能映射到相同的哈希值。
3. 鸽巢原理（Pigeonhole Principle）：如果有 N 个键，但只有 M 个桶（N > M），则必定存在 至少两个键映射到同一个桶。

🚀 示例

假设哈希表有 5 个桶（索引 0 ~ 4），我们使用哈希函数：

hash(key) = key % 5

📌 哈希值计算

Key = 10  → hash(10) = 10 % 5 = 0
Key = 15  → hash(15) = 15 % 5 = 0 （冲突）

✅ 键 10 和 15 发生哈希冲突，因为它们映射到同一个索引 0。

📌 哈希冲突（Hash Collision）

哈希冲突 发生在 两个不同的键（Key）映射到同一个哈希值（Bucket 位置） 的情况。在 hashtable（哈希表）中，哈希冲突是 不可避免 的，因为哈希函数的值域（桶的数量）通常小于可能的键值域。

📌 1. 为什么会发生哈希冲突？

🚀 1.1 哈希函数的有限性

• 哈希函数 hash(key) % bucket_count 计算出的哈希值 在 bucket_count 之内。
• 但可能的 键空间（key space）远远大于 bucket_count。

📌 示例

hash("apple") % 10  → 3
hash("orange") % 10 → 3  (冲突)

🔹 “apple” 和 “orange” 的哈希值相同，导致哈希冲突！

📌 2. 解决哈希冲突的方法

哈希表常用的哈希冲突解决方案有两种：

1. 链地址法（Chaining）
2. 开放寻址法（Open Addressing）

📌 3. 链地址法（Chaining）

🔹 思路：

• 每个哈希桶（Bucket）存储一个链表（linked list）。
• 当多个键值对映射到同一个桶时，使用链表存储多个元素。

🚀 示例

哈希桶（bucket）：
 ┌───────┬───────┬───────┬───────┬───────┐
 │  0    │  1    │  2    │  3    │  4    │  
 └───┬───┴───┬───┴───┬───┴───┬───┴───┬───┘
     ↓       ↓       ↓       ↓       ↓
  [Key1, Val1] → [Key5, Val5]   NULL   [Key2, Val2] → [Key6, Val6]

📌 代码实现

#include <iostream>
#include <vector>
#include <list>

class HashTable {
private:
    std::vector<std::list<int>> table;
    size_t bucket_count;

    size_t hash_function(int key) { return key % bucket_count; }

public:
    HashTable(size_t size) : bucket_count(size) { table.resize(bucket_count); }

    void insert(int key) {
        size_t index = hash_function(key);
        table[index].push_back(key); // 追加到链表
    }

    void display() {
        for (size_t i = 0; i < bucket_count; i++) {
            std::cout << "Bucket " << i << ": ";
            for (int val : table[i])
                std::cout << val << " -> ";
            std::cout << "NULL\n";
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(1);
    ht.insert(6);  // 冲突，进入相同链表
    ht.insert(11); // 冲突，进入相同链表
    ht.display();
}

📌 输出

Bucket 0: NULL
Bucket 1: 1 -> 6 -> 11 -> NULL
Bucket 2: NULL
Bucket 3: NULL
Bucket 4: NULL

✅ 链地址法 可以有效减少哈希冲突，但 链表可能变长，影响查找性能（最坏 O(N)）。

📌 4. 开放寻址法（Open Addressing）

🔹 思路：

• 当冲突发生时，不使用链表，而是在哈希表内寻找下一个空位置存放元素。
• 探测（Probing）策略：
  • 线性探测（Linear Probing）：index = (index + 1) % bucket_count
  • 二次探测（Quadratic Probing）：index = (index + i^2) % bucket_count
  • 双重哈希（Double Hashing）：index = (index + i * hash2(key)) % bucket_count

🚀 4.1 线性探测（Linear Probing）

📌 代码实现

#include <iostream>
#include <vector>

class HashTable {
private:
    std::vector<int> table;
    size_t bucket_count;

    size_t hash_function(int key) { return key % bucket_count; }

public:
    HashTable(size_t size) : bucket_count(size), table(size, -1) {} // -1 表示空位

    void insert(int key) {
        size_t index = hash_function(key);
        while (table[index] != -1) {  // 线性探测寻找下一个空位
            index = (index + 1) % bucket_count;
        }
        table[index] = key;
    }

    void display() {
        for (size_t i = 0; i < bucket_count; i++)
            std::cout << "Bucket " << i << ": " << (table[i] == -1 ? "NULL" : std::to_string(table[i])) << "\n";
    }
};

int main() {
    HashTable ht(5);
    ht.insert(1);
    ht.insert(6);  // 冲突，寻找下一个空位
    ht.insert(11); // 冲突，寻找下一个空位
    ht.display();
}

📌 输出

Bucket 0: NULL
Bucket 1: 1
Bucket 2: 6
Bucket 3: 11
Bucket 4: NULL

✅ 线性探测避免了链表，但可能导致 聚集问题（Clustering），查询性能下降。

🚀 4.2 二次探测（Quadratic Probing）

• 使用 二次方递增查找空位：

index = (index + i^2) % bucket_count;

• 解决线性探测的聚集问题。

📌 代码实现

size_t index = hash_function(key);
size_t i = 0;
while (table[index] != -1) {
    i++;
    index = (index + i * i) % bucket_count;  // 二次探测
}

✅ 适用于负载因子较低的情况。

🚀 4.3 双重哈希（Double Hashing）

• 使用 两个哈希函数 解决冲突：

index = (index + i * hash2(key)) % bucket_count;

• 避免一次哈希函数导致的聚集问题。
• 适用于 负载因子较高的情况（适合 hash2(key) 互质的素数）。

📌 代码示例

size_t hash2(int key) { return 7 - (key % 7); } // 第二个哈希函数

size_t index = hash_function(key);
size_t i = 0;
while (table[index] != -1) {
    i++;
    index = (index + i * hash2(key)) % bucket_count;  // 双重哈希
}

✅ 比线性探测更好，但计算复杂度更高。

📌 5. 哈希冲突的选择

🚀 STL unordered_map 采用 链地址法（Chaining）！
🚀 数据库索引、缓存系统常用 双重哈希（Double Hashing）！