1. 引言哈希表Hash Table是计算机科学中一种非常重要的数据结构它通过哈希函数将键Key映射到存储位置从而实现近乎常数时间复杂度的查找、插入和删除操作。在C标准库中std::unordered_map和std::unordered_set就是基于哈希表实现的容器。理解哈希表的底层原理对于深入掌握C编程、优化程序性能以及应对技术面试都至关重要。本文将带领大家从零开始用C实现一个简易的哈希表。我们将逐步讲解哈希函数的设计、冲突解决方法、扩容机制等核心概念并提供完整的代码示例。无论你是C初学者还是希望巩固数据结构知识的开发者这篇文章都将为你提供清晰的指引。2. 哈希表的核心概念2.1 什么是哈希表哈希表的基本思想是通过一个哈希函数h(key)将任意大小的键如字符串、对象转换成一个固定范围的整数索引然后将键值对存储在该索引对应的数组位置通常称为“桶”或“槽”中。理想情况下这个操作的时间复杂度是O(1)。2.2 哈希函数一个好的哈希函数应该满足确定性相同的键必须产生相同的哈希值。均匀性哈希值应尽可能均匀分布在数组范围内以减少冲突。高效性计算速度快。对于整数键可以直接取模对于字符串键常用如BKDR、DJB2等算法。2.3 哈希冲突当两个不同的键经过哈希函数计算后得到相同的索引时就发生了“哈希冲突”。解决冲突的常见方法有链地址法每个桶维护一个链表或其他容器所有映射到该桶的键值对都存储在这个链表中。开放地址法当发生冲突时按照某种探测序列如线性探测、二次探测寻找下一个空闲的桶。本文将采用实现相对简单且常用的链地址法。3. 实现步骤3.1 定义哈希表节点首先我们需要定义存储键值对的节点结构。每个节点包含键、值和指向下一个节点的指针用于构建链表。template typename K, typename V struct HashNode { K key; V value; HashNode* next; HashNode(const K k, const V v) : key(k), value(v), next(nullptr) {} };3.2 哈希表类框架接下来定义哈希表类的基本框架包括私有成员和公有接口。template typename K, typename V class HashTable { private: // 桶数组每个元素是一个链表头指针 std::vectorHashNodeK, V* table; // 当前存储的键值对数量 size_t numElements; // 桶的数量 size_t tableSize; // 哈希函数简易版针对整数和字符串特化 size_t hashFunction(const K key) const; // 扩容 void rehash(); public: // 构造函数与析构函数 HashTable(size_t size 101); ~HashTable(); // 基本操作 void insert(const K key, const V value); bool find(const K key, V value) const; bool remove(const K key); size_t size() const { return numElements; } bool empty() const { return numElements 0; } // 打印哈希表内容调试用 void print() const; };3.3 实现哈希函数我们实现一个简单的哈希函数。对于整数直接取模对于std::string使用一个简单的循环累加算法实际项目中应使用更成熟的算法。template typename K, typename V size_t HashTableK, V::hashFunction(const K key) const { // 通用版本使用std::hash std::hashK hasher; return hasher(key) % tableSize; } // 可以为std::string提供特化版本示例 template size_t HashTablestd::string, int::hashFunction(const std::string key) const { size_t hash 0; for (char c : key) { hash hash * 31 c; // 一个简单的乘数哈希 } return hash % tableSize; }3.4 实现插入操作插入操作的步骤计算键的哈希值找到对应的桶。遍历该桶的链表检查键是否已存在。如果存在更新值。如果不存在在链表头部插入新节点。更新元素数量并检查负载因子元素数/桶数如果超过阈值如0.75则触发扩容rehash。template typename K, typename V void HashTableK, V::insert(const K key, const V value) { // 检查是否需要扩容 if (numElements tableSize * 0.75) { rehash(); } size_t index hashFunction(key); HashNodeK, V* node table[index]; // 遍历链表查找是否已存在该key while (node ! nullptr) { if (node-key key) { node-value value; // 更新值 return; } node node-next; } // key不存在在链表头部插入新节点 HashNodeK, V* newNode new HashNodeK, V(key, value); newNode-next table[index]; table[index] newNode; numElements; }3.5 实现查找和删除操作查找和删除操作也需要遍历链表处理找到和未找到的情况。template typename K, typename V bool HashTableK, V::find(const K key, V value) const { size_t index hashFunction(key); HashNodeK, V* node table[index]; while (node ! nullptr) { if (node-key key) { value node-value; return true; } node node-next; } return false; } template typename K, typename V bool HashTableK, V::remove(const K key) { size_t index hashFunction(key); HashNodeK, V* node table[index]; HashNodeK, V* prev nullptr; while (node ! nullptr) { if (node-key key) { if (prev nullptr) { // 要删除的是头节点 table[index] node-next; } else { prev-next node-next; } delete node; --numElements; return true; } prev node; node node-next; } return false; // 未找到 }3.6 实现扩容Rehash当负载因子过高时需要创建一个更大的桶数组并将所有现有元素重新哈希到新数组中。template typename K, typename V void HashTableK, V::rehash() { size_t newSize tableSize * 2 1; // 通常取一个素数更好这里简单处理 std::vectorHashNodeK, V* newTable(newSize, nullptr); for (size_t i 0; i tableSize; i) { HashNodeK, V* node table[i]; while (node ! nullptr) { HashNodeK, V* next node-next; // 在新表中计算新的索引 size_t newIndex std::hashK{}(node-key) % newSize; // 插入到新桶的头部 node-next newTable[newIndex]; newTable[newIndex] node; node next; } } // 交换新旧表 table.swap(newTable); tableSize newSize; // newTable 离开作用域其旧指针已被清空无需手动删除 }3.7 构造函数、析构函数与打印函数template typename K, typename V HashTableK, V::HashTable(size_t size) : tableSize(size), numElements(0) { table.resize(tableSize, nullptr); } template typename K, typename V HashTableK, V::~HashTable() { for (size_t i 0; i tableSize; i) { HashNodeK, V* node table[i]; while (node ! nullptr) { HashNodeK, V* temp node; node node-next; delete temp; } } } template typename K, typename V void HashTableK, V::print() const { for (size_t i 0; i tableSize; i) { std::cout Bucket[ i ]: ; HashNodeK, V* node table[i]; while (node ! nullptr) { std::cout ( node-key , node-value ) - ; node node-next; } std::cout nullptr std::endl; } }4. 测试示例下面是一个简单的测试程序演示哈希表的基本用法。#include iostream #include string int main() { HashTablestd::string, int ht; // 插入操作 ht.insert(Alice, 85); ht.insert(Bob, 92); ht.insert(Charlie, 78); ht.insert(David, 88); ht.insert(Alice, 90); // 更新Alice的成绩 std::cout HashTable size: ht.size() std::endl; // 查找操作 int score; if (ht.find(Bob, score)) { std::cout Bobs score: score std::endl; } // 删除操作 if (ht.remove(Charlie)) { std::cout Charlie removed. std::endl; } // 打印哈希表内容 ht.print(); return 0; }5. 总结与进阶至此我们完成了一个支持插入、查找、删除和动态扩容的简易哈希表。这个实现采用了链地址法解决冲突并使用std::vector和原始指针管理内存。当然一个工业级的哈希表还需要考虑更多细节更优的哈希函数针对特定数据类型设计减少冲突。迭代器支持使其能够像STL容器一样使用范围for循环。异常安全确保在异常发生时资源不会泄漏。移动语义支持移动构造和移动赋值提升性能。桶大小的选择使用素数作为桶大小可以使哈希分布更均匀。希望通过这个从零开始的实现过程你能对哈希表的工作原理有更深刻的理解。接下来你可以尝试在此基础上添加新功能或者直接研究C标准库中std::unordered_map的源码对比学习。学习数据结构最好的方式就是动手实现。加油你的C之路又前进了一步