哈希表与散列表的原理及C++实现

1. 什么是哈希表？

哈希表（Hash Table）是一种高效的数据结构，用于存储键值对（Key-Value Pairs）。它通过哈希函数（Hash Function）将键（Key）映射到一个固定大小的数组（称为散列表）中的某个位置，从而实现快速的插入、查找和删除操作。

哈希表的核心思想是通过哈希函数将键转换为数组的索引，从而直接访问对应的值。理想情况下，哈希表的插入、查找和删除操作的时间复杂度都是 O(1)。

2. 哈希表的核心概念

2.1 哈希函数（Hash Function）

哈希函数是哈希表的核心，它负责将任意大小的键映射到一个固定范围的整数（通常是数组的索引）。一个好的哈希函数应满足以下条件：

1. 均匀分布：哈希值应尽可能均匀地分布在数组中，以减少冲突。
2. 高效计算：哈希函数的计算应尽可能快。
3. 一致性：相同的键应始终映射到相同的哈希值。

2.2 散列表（Hash Table）

散列表是一个数组，用于存储键值对。哈希函数将键映射到数组的某个索引，然后将值存储在该索引对应的位置。

2.3 冲突（Collision）

由于哈希函数的输出范围有限，而键的范围可能很大，因此不同的键可能会映射到相同的索引，这种现象称为冲突。常见的冲突解决方法包括：

1. 链地址法（Chaining）：将冲突的键值对存储在同一个索引位置的链表中。
2. 开放地址法（Open Addressing）：通过探测方法（如线性探测、二次探测）在散列表中寻找下一个可用的位置。

3. 哈希表的实现

下面我们使用 链地址法 来实现一个简单的哈希表，并用 C++ 代码演示其操作。

3.1 C++ 实现

#include <iostream>
#include <list>
#include <vector>
#include <utility> // for std::pair

class HashTable {
private:
    static const int TABLE_SIZE = 10; // 散列表的大小
    std::vector<std::list<std::pair<int, std::string>>> table; // 使用链表解决冲突

    // 哈希函数
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

public:
    HashTable() : table(TABLE_SIZE) {}

    // 插入键值对
    void insert(int key, const std::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); // 否则插入新的键值对
    }

    // 查找键对应的值
    std::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 printTable() const {
        for (int i = 0; i < TABLE_SIZE; ++i) {
            std::cout << "Bucket " << i << ": ";
            for (const auto& pair : table[i]) {
                std::cout << "(" << pair.first << ", " << pair.second << ") ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    HashTable hashTable;

    // 插入键值对
    hashTable.insert(1, "Alice");
    hashTable.insert(2, "Bob");
    hashTable.insert(11, "Charlie"); // 11 和 1 会发生冲突
    hashTable.insert(12, "David");   // 12 和 2 会发生冲突

    // 打印散列表
    std::cout << "Hash Table Contents:" << std::endl;
    hashTable.printTable();

    // 查找键
    std::cout << "Search for key 11: " << hashTable.search(11) << std::endl;
    std::cout << "Search for key 3: " << hashTable.search(3) << std::endl;

    // 删除键
    hashTable.remove(11);
    std::cout << "After removing key 11:" << std::endl;
    hashTable.printTable();

    return 0;
}

运行结果：

Hash Table Contents:
Bucket 0: 
Bucket 1: (1, Alice) (11, Charlie) 
Bucket 2: (2, Bob) (12, David) 
Bucket 3: 
Bucket 4: 
Bucket 5: 
Bucket 6: 
Bucket 7: 
Bucket 8: 
Bucket 9: 
Search for key 11: Charlie
Search for key 3: Not Found
After removing key 11:
Bucket 0: 
Bucket 1: (1, Alice) 
Bucket 2: (2, Bob) (12, David) 
Bucket 3: 
Bucket 4: 
Bucket 5: 
Bucket 6: 
Bucket 7: 
Bucket 8: 
Bucket 9: 

3.2 代码解析

1. 哈希函数：

   • 使用简单的取模运算 key % TABLE_SIZE 将键映射到散列表的索引。

2. 冲突解决：

   • 使用链地址法，每个索引位置存储一个链表，链表中存放所有映射到该索引的键值对。

3. 插入操作：

   • 计算键的哈希值，找到对应的索引。
   • 如果键已存在，更新其值；否则将新的键值对插入链表。

4. 查找操作：

   • 计算键的哈希值，遍历对应索引位置的链表，查找键是否存在。

5. 删除操作：

   • 计算键的哈希值，遍历对应索引位置的链表，删除匹配的键值对。

6. 打印散列表：

   • 遍历散列表，打印每个索引位置的链表内容。

4. 哈希表的性能分析

• 时间复杂度：

  • 插入、查找和删除的平均时间复杂度为 O(1)。
  • 在最坏情况下（所有键都映射到同一个索引），时间复杂度退化为 O(n)。

• 空间复杂度：

  • 空间复杂度为 O(n)，其中 n 是键值对的数量。

5. 哈希表的应用场景

• 字典：存储键值对，支持快速查找。
• 缓存：如 LRU 缓存，利用哈希表实现快速访问。
• 数据库索引：哈希表可用于实现数据库的索引结构。
• 去重：利用哈希表快速判断元素是否已存在。

6. 总结

哈希表是一种高效的数据结构，通过哈希函数将键映射到数组索引，从而实现快速的插入、查找和删除操作。链地址法是解决冲突的常见方法之一，适合处理哈希冲突的情况。

7.练习

ACWing模拟散列表
这里我们展示一种不使用STL的链表写法。使用STL可以使用map，unordered_map等快速解决，或者像上文中提到的vector模拟链表。这里我们使用的是一种链式结构记录。数据结构书本上链表需要不断malloc，在算法比赛当中是不合适的，因为会消耗大量的时间。这种链式结构的原理如下：

1. 插入操作 (insert 函数)

1. 计算哈希值：通过 (num % mod + mod) % mod 计算键 num 的哈希值 pos。
2. 更新 head：head 自增，表示新节点的索引。
3. 链式插入：
   • 将新节点的 nxt 指向当前 h[pos]（即链表的头部）。
   • 更新 h[pos] 为 head，表示新节点成为链表的头部。
   • 将 e[head] 赋值为 num，存储键值。
4. 结束：插入操作完成。

假设现在状态如此，我们来模拟插入新来的一个编号为8的节点的过程。

• 首先计算8号节点的位置，假设经过哈希之后，需要放在5号桶。
• 接着，根据代码的操作，先将8号节点的nxt[8] 指向当前5号桶的头部节点7，并更新头部为5号桶头部节点为8号节点，再把值存入e数组的一个空位置。
• 完成操作后，链表的形式如下图所示
  

2. 查询操作 (query 函数)

1. 计算哈希值：通过 (num % mod + mod) % mod 计算键 num 的哈希值 pos。
2. 初始化遍历：从 h[pos] 开始遍历链表。
3. 遍历链表：
   • 如果当前节点的值 e[i] 等于 num，返回 true。
   • 否则，移动到下一个节点 i = nxt[i]。
4. 遍历结束：如果遍历完链表仍未找到 num，返回 false。

代码逻辑总结

• h[pos]：存储哈希值为 pos 的链表的头节点索引。
• nxt[i]：存储索引为 i 的节点的下一个节点索引。
• e[i]：存储索引为 i 的节点的值。
• head：表示当前可用的节点索引，每次插入时自增。

通过链式结构，哈希表可以高效地处理冲突，并支持动态插入和查询操作。

具体代码实现如下

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7;
const int mod = 1e5 + 7;
int h[maxn], e[maxn], nxt[maxn], head = 0;
void insert(int num){
    int pos = (num % mod + mod) % mod;
    nxt[++head] = h[pos];
    h[pos] = head;
    e[head] = num;
}
bool query(int num){
    int pos = (num % mod + mod) % mod;
    for(int i = h[pos];i!=-1;i=nxt[i]){
        if(e[i] == num)
            return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(h, -1, sizeof(h));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string op;
        int num;
        //scanf("%s %d", op, &num);
        cin>>op>>num;
        if(op == "I"){
            if(!query(num))
                insert(num);
        }
        else{
            if(query(num))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}