1. 哈希表（Hash Table）

1.1 基本概念

哈希表是一种通过哈希函数将键(key)映射到表中特定位置来访问记录的数据结构。它提供了平均时间复杂度为O(1)的查找、插入和删除操作。

1.2 核心组成

1. 键(Key): 用于查找和标识数据的唯一标识符

2. 值(Value): 与键关联的实际数据

3. 哈希函数(Hash Function): 将键转换为数组索引的函数

4. 哈希桶(Buckets): 存储键值对的容器数组

5. 冲突解决机制: 处理多个键映射到同一索引的情况

1.3 工作原理

键 → 哈希函数 → 哈希值 → 数组索引 → 存储/检索值

1.4 性能特点

• 平均时间复杂度:

• 插入: O(1)

• 查找: O(1)

• 删除: O(1)

• 最坏情况时间复杂度: O(n) (当所有键都冲突时)

2. 哈希函数（Hash Function）

2.1 基本概念

哈希函数是将任意大小的数据映射到固定大小值的函数。在哈希表中，它将键转换为数组索引。

2.2 理想哈希函数的特性

1. 确定性: 相同的键总是产生相同的哈希值

2. 均匀性: 哈希值应均匀分布在输出空间

3. 高效性: 计算速度快

4. 抗碰撞性: 不同键产生相同哈希值的概率低

2.3 常见哈希函数类型

2.3.1 除法哈希法

hash(key) = key % table_size

2.3.2 乘法哈希法

hash(key) = floor(table_size * (key * A - floor(key * A))) 
其中 0 < A < 1

2.3.3 通用哈希法

hash(key) = ((a * key + b) % p) % table_size其中p是大素数，a,b是随机数

2.3.4 字符串哈希函数

// DJB2哈希函数
unsigned long djb2_hash(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

2.4 哈希函数设计原则

1. 考虑键的类型: 整数、字符串、对象等需要不同的处理

2. 利用键的所有信息: 确保键的每个部分都影响哈希值

3. 避免规律性: 防止键的模式导致哈希值聚集

4. 测试均匀性: 实际测试哈希值分布情况

2.5 哈希表与平衡树的比较

实现方式：

#include <unordered_map> // 哈希表
#include <unordered_set> // 哈希集合

int main() {
    // 哈希表示例
    std::unordered_map<std::string, int> wordCount;
    
    // 插入元素
    wordCount["apple"] = 5;
    wordCount.insert({"banana", 3});
    
    // 查找元素
    if(wordCount.find("apple") != wordCount.end()) {
        std::cout << "apple count: " << wordCount["apple"] << std::endl;
    }
    
    // 哈希集合示例
    std::unordered_set<int> uniqueNumbers;
    uniqueNumbers.insert(1);
    uniqueNumbers.insert(2);
    uniqueNumbers.insert(1); // 重复元素不会被插入
    
    return 0;
}