C++中哈希表（Hash Table）相关内容的目录或提纲

zhxup606

585人浏览 · 2025-10-02 08:28:22

zhxup606 · 2025-10-02 08:28:22 发布

C++中哈希表（Hash Table）相关内容的目录或提纲，总结或讨论哈希表的概念与实现。我将根据这个提纲，简要概述每一部分的内容，并提供简单的C++代码示例来帮助你理解哈希表的核心概念和实现。如果你有具体问题或需要更深入的代码实现，请告诉我！

前言

哈希表是一种高效的数据结构，用于快速查找、插入和删除数据。它的核心思想是通过哈希函数将键映射到存储位置，平均时间复杂度可达到O(1)。以下是提纲中各部分的解释和代码实现。

1. 哈希表的概念

1.1 哈希函数（Hash Function）：哈希表的 “地址映射引擎”

哈希函数是将键（key）映射到存储位置（索引）的函数。好的哈希函数应具有：

均匀性：键均匀分布到表中，减少冲突。
高效性：计算速度快。
确定性：同一键总是映射到同一位置。

常见哈希函数：

整数键：取模（key % table_size）。
字符串键：累加字符的ASCII值后取模，或使用多项式哈希。

1.2 哈希冲突（Hash Collision）：哈希函数的 “必然产物”

当不同键映射到同一位置时，发生哈希冲突。冲突不可避免，但可以通过以下方式解决：

开放寻址法：在表内寻找下一个空位。
链地址法：在同一索引处存储链表。

1.3 负载因子（Load Factor）：衡量 “数据拥挤程度” 的核心指标

负载因子 = 元素数量 / 哈希表大小。负载因子过高会导致冲突增加，通常需要动态调整表大小（扩容）。常见阈值为0.75。

2. 哈希函数

2.1 直接定址法（Direct Addressing）

直接将键作为索引，适用于键的范围较小且连续的情况。

优点：无冲突，O(1)查询。
缺点：空间浪费严重。

示例代码（简单直接定址）：

#include <iostream>
#include <vector>

class DirectAddressTable {
    std::vector<int> table;
public:
    DirectAddressTable(int size) : table(size, -1) {} // -1表示空
    void insert(int key, int value) { table[key] = value; }
    int get(int key) { return table[key]; }
};

int main() {
    DirectAddressTable dat(1000);
    dat.insert(42, 100);
    std::cout << "Value at key 42: " << dat.get(42) << std::endl; // 输出100
    return 0;
}

2.2 除留余数法（Division Method）

用键除以表大小，取余数作为索引：index = key % table_size。

优点：简单，适用于大多数情况。
缺点：需要选择合适的表大小（最好是质数）以减少冲突。

2.3 其他方法

乘法哈希：index = floor(table_size * (key * A % 1))，其中A是黄金分割比（约0.618）。
多项式哈希：常用于字符串，累加字符值并乘以固定常数。
折叠法：将键分割成几部分，累加后取模。

3. 哈希冲突

3.1 开放寻址法（Open Addressing）

当发生冲突时，通过某种探测策略（如线性探测、二次探测或双重哈希）寻找下一个空位。

线性探测：index = (index + 1) % table_size。
优点：实现简单，适合小规模数据。
缺点：容易产生聚集（clustering），性能下降。

简单的代码实现（线性探测）：

#include <iostream>
#include <vector>

class HashTableOpenAddressing {
    std::vector<std::pair<int, int>> table; // 存储键值对
    int size;
public:
    HashTableOpenAddressing(int s) : size(s), table(s, {-1, -1}) {}
    
    int hash(int key) { return key % size; }
    
    void insert(int key, int value) {
        int index = hash(key);
        while (table[index].first != -1) { // 寻找空位
            index = (index + 1) % size; // 线性探测
        }
        table[index] = {key, value};
    }
    
    int find(int key) {
        int index = hash(key);
        int start = index;
        while (table[index].first != key && table[index].first != -1) {
            index = (index + 1) % size;
            if (index == start) return -1; // 表满或未找到
        }
        return table[index].first == key ? table[index].second : -1;
    }
};

int main() {
    HashTableOpenAddressing ht(10);
    ht.insert(1, 100);
    ht.insert(11, 200); // 冲突，线性探测
    std::cout << "Value for key 11: " << ht.find(11) << std::endl; // 输出200
    return 0;
}

3.2 链地址法（Chaining）

每个哈希表位置存储一个链表，冲突的键值对追加到链表中。

优点：简单，性能稳定。
缺点：需要额外空间存储链表。

简单的代码实现（链地址法）：

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

class HashTableChaining {
    std::vector<std::list<std::pair<int, int>>> table;
    int size;
public:
    HashTableChaining(int s) : size(s), table(s) {}
    
    int hash(int key) { return key % size; }
    
    void insert(int key, int value) {
        int index = hash(key);
        table[index].push_back({key, value});
    }
    
    int find(int key) {
        int index = hash(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) return pair.second;
        }
        return -1; // 未找到
    }
};

int main() {
    HashTableChaining ht(10);
    ht.insert(1, 100);
    ht.insert(11, 200); // 冲突，加入同一链表
    std::cout << "Value for key 11: " << ht.find(11) << std::endl; // 输出200
    return 0;
}