哈希表（Hash Table）是一种数据结构，它通过哈希函数将键映射到表中的一个位置（通常称为桶），使得数据的插入、删除和查找操作的时间复杂度接近常数时间 O(1)。哈希表广泛应用于实现字典、集合、缓存等场景。

哈希表基本原理

1. 哈希函数：

   • 哈希表的核心是哈希函数，它将数据的键（key）映射到数组的索引（index）。理想情况下，哈希函数应当能均匀地将数据分布到整个哈希表中，减少碰撞的发生。

2. 碰撞（Collision）：

   • 当多个键映射到同一个数组索引时，称为碰撞。碰撞的处理方法有两种常见的策略：
     • 链式法（Separate Chaining）：每个桶（数组位置）存储一个链表（或其他容器），所有映射到相同位置的键值对都存储在这个链表中。
     • 开放地址法（Open Addressing）：如果发生碰撞，尝试寻找其他空闲位置存储元素，常用的方法有线性探测、二次探测和双重哈希等。

3. 负载因子（Load Factor）：

   • 负载因子是哈希表的大小与存储元素个数的比例。负载因子过大，容易发生碰撞，负载因子过小，则空间浪费。一般来说，当负载因子达到某个阈值时，哈希表会进行扩容。

1. 哈希表实现（链式法）

在这里，我们采用链式法来处理碰撞问题。每个哈希桶会存储一个链表，当发生碰撞时，直接在链表中添加元素。

1.1 代码实现

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;

class HashTable {
private:
    vector<list<pair<int, string>>> table;  // 使用链表存储哈希冲突
    int size;  // 哈希表的大小
    
    // 哈希函数，简单实现，返回键的取模
    int hashFunction(int key) {
        return key % size;
    }
    
public:
    // 构造函数
    HashTable(int s) : size(s) {
        table.resize(size);
    }
    
    // 插入元素
    void insert(int key, const string& value) {
        int index = hashFunction(key);
        // 查找是否存在相同的键
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                pair.second = value;  // 如果已经存在，更新值
                return;
            }
        }
        table[index].emplace_back(key, value);  // 如果没有，插入新元素
    }
    
    // 查找元素
    string search(int key) {
        int index = hashFunction(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return "Not found";  // 如果没有找到
    }
    
    // 删除元素
    void remove(int key) {
        int index = hashFunction(key);
        auto& chain = table[index];
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if (it->first == key) {
                chain.erase(it);
                return;
            }
        }
    }

    // 打印哈希表
    void print() {
        for (int i = 0; i < size; ++i) {
            cout << "Bucket " << i << ": ";
            for (const auto& pair : table[i]) {
                cout << "(" << pair.first << ", " << pair.second << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    HashTable ht(10);  // 创建哈希表，大小为10
    
    ht.insert(1, "Alice");
    ht.insert(2, "Bob");
    ht.insert(12, "Charlie");  // 12 和 2 会映射到相同的桶
    ht.insert(22, "David");  // 22 和 2 会映射到相同的桶
    
    cout << "Search key 1: " << ht.search(1) << endl;
    cout << "Search key 2: " << ht.search(2) << endl;
    cout << "Search key 12: " << ht.search(12) << endl;
    
    ht.remove(2);  // 删除键为2的元素
    cout << "After removal:" << endl;
    ht.print();  // 打印哈希表
    
    return 0;
}

1.2 代码解释

1. 哈希函数：hashFunction(int key) 函数通过取模操作将键映射到哈希表中的某个位置。简单来说，哈希值为 key % size。

2. 插入操作：通过哈希函数得到桶的索引，然后将元素（键值对）插入到对应桶的链表中。如果链表中已经存在相同的键，就更新值。

3. 查找操作：根据键计算哈希值并定位到对应桶，然后在链表中查找是否有该键。

4. 删除操作：根据键计算哈希值并定位到对应桶，遍历链表，找到并删除指定键的元素。

5. 打印哈希表：通过遍历哈希表中的所有桶，输出每个桶中的元素。

2. 哈希表扩展：开放地址法（线性探测）

开放地址法在发生碰撞时，尝试寻找下一个空位置，常用的探测方法有线性探测、二次探测和双重哈希等。这里我们以线性探测为例，展示开放地址法。

2.1 代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class OpenAddressingHashTable {
private:
    vector<pair<int, string>> table;  // 哈希表
    vector<bool> occupied;  // 标记位置是否被占用
    int size;
    
    // 哈希函数
    int hashFunction(int key) {
        return key % size;
    }

public:
    // 构造函数
    OpenAddressingHashTable(int s) : size(s) {
        table.resize(size, {-1, ""});
        occupied.resize(size, false);
    }

    // 插入操作
    void insert(int key, const string& value) {
        int index = hashFunction(key);
        int start = index;  // 保存起始位置，防止在循环中找不到空位
        while (occupied[index]) {
            if (table[index].first == key) {
                table[index].second = value;  // 更新值
                return;
            }
            index = (index + 1) % size;  // 线性探测
            if (index == start) return;  // 防止死循环
        }
        table[index] = {key, value};
        occupied[index] = true;
    }

    // 查找操作
    string search(int key) {
        int index = hashFunction(key);
        int start = index;
        while (occupied[index]) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % size;
            if (index == start) break;
        }
        return "Not found";
    }

    // 删除操作
    void remove(int key) {
        int index = hashFunction(key);
        int start = index;
        while (occupied[index]) {
            if (table[index].first == key) {
                table[index] = {-1, ""};  // 删除元素
                occupied[index] = false;
                return;
            }
            index = (index + 1) % size;
            if (index == start) break;
        }
    }

    // 打印哈希表
    void print() {
        for (int i = 0; i < size; ++i) {
            if (occupied[i]) {
                cout << "Index " << i << ": (" << table[i].first << ", " << table[i].second << ")" << endl;
            }
        }
    }
};

int main() {
    OpenAddressingHashTable ht(10);  // 创建哈希表，大小为10

    ht.insert(1, "Alice");
    ht.insert(2, "Bob");
    ht.insert(12, "Charlie");  // 12 会与 2 发生碰撞
    ht.insert(22, "David");   // 22 会与 2 发生碰撞
    
    cout << "Search key 1: " << ht.search(1) << endl;
    cout << "Search key 2: " << ht.search(2) << endl;
    cout << "Search key 12: " << ht.search(12) << endl;

    ht.remove(2);  // 删除键为2的元素


    cout << "After removal:" << endl;
    ht.print();  // 打印哈希表

    return 0;
}

2.2 代码解释

1. 哈希函数：与前面相同，使用 key % size 来计算哈希值。
2. 插入操作：如果位置已被占用，使用线性探测查找下一个空位置。若找到相同的键，更新值。
3. 查找操作：使用相同的线性探测方法查找目标键。如果碰到空位置或者回到起始位置，表示未找到。
4. 删除操作：删除元素时，将位置标记为空，并重新调整后续的元素。

3. 总结

哈希表是高效的查找数据结构，尤其适用于需要快速插入、删除和查找操作的场景。常见的碰撞解决方法有链式法和开放地址法，其中链式法通过链表来处理碰撞，而开放地址法通过探测空位置来处理碰撞。根据应用的不同，选择合适的哈希表实现可以大大提高程序的效率。