当前位置：首页 > news >正文

C++哈希表封装实战指南

news 2026/4/12 23:53:20

【哈希表封装实现】—— 我与C++的不解之缘（二十九）

在C++编程中，哈希表是一种高效的数据结构，用于存储键值对（key-value pairs）。它通过哈希函数快速定位数据，平均时间复杂度为$O(1)$。本文将逐步介绍哈希表的原理、封装实现方法，并提供完整的C++代码示例。文章结构清晰，帮助您深入理解并实践哈希表在C++中的应用。

1. 哈希表基本原理

哈希表的核心是哈希函数（hash function），它将键映射到数组索引位置。理想情况下，哈希函数应均匀分布键，减少冲突（collision）。例如，一个简单的哈希函数可定义为： $$ h(k) = k \mod m $$ 其中，$k$是键值，$m$是哈希表的大小。冲突发生时，常用解决方法包括：

链地址法（Chaining）：每个数组元素指向一个链表，存储冲突的键值对。
开放地址法（Open Addressing）：在数组中寻找下一个空槽位。

哈希表的性能依赖于负载因子（load factor），定义为： $$ \lambda = \frac{n}{m} $$ 其中，$n$是元素数量，$m$是表大小。当$\lambda$超过阈值（如0.7）时，需进行重哈希（rehashing）以扩容。

2. C++中的封装实现

在C++中，我们可以封装一个自定义哈希表类，实现基本操作如插入、查找和删除。设计思路包括：

类结构：定义HashTable类，包含私有成员如数组（桶）和公共方法。
冲突解决：这里采用链地址法，使用std::list存储键值对。
哈希函数：实现一个简单的哈希函数，确保键均匀分布。

以下是一个完整的封装实现代码示例：

#include <iostream> #include <list> #include <vector> template <typename K, typename V> class HashTable { private: int capacity; // 哈希表容量 std::vector<std::list<std::pair<K, V>>> table; // 桶数组，每个桶是一个链表 // 哈希函数：计算键的索引 int hashFunction(K key) { return std::hash<K>{}(key) % capacity; } public: // 构造函数，初始化容量和表 HashTable(int cap = 10) : capacity(cap) { table.resize(capacity); } // 插入键值对 void insert(K key, V value) { int index = hashFunction(key); auto& bucket = table[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { // 键已存在，更新值 it->second = value; return; } } bucket.push_back(std::make_pair(key, value)); // 新键，添加到链表 } // 查找键的值，返回指针或nullptr V* get(K key) { int index = hashFunction(key); auto& bucket = table[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { return &(it->second); } } return nullptr; // 未找到 } // 删除键值对 bool remove(K key) { int index = hashFunction(key); auto& bucket = table[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { bucket.erase(it); return true; } } return false; // 未找到 } // 打印表内容（调试用） void print() { for (int i = 0; i < capacity; ++i) { std::cout << "Bucket " << i << ": "; for (auto& pair : table[i]) { std::cout << "[" << pair.first << ":" << pair.second << "] "; } std::cout << std::endl; } } }; int main() { HashTable<std::string, int> ht; // 示例：字符串键，整数值 ht.insert("apple", 10); ht.insert("banana", 20); ht.insert("apple", 15); // 更新现有键 ht.print(); int* val = ht.get("banana"); if (val) std::cout << "Value: " << *val << std::endl; ht.remove("apple"); return 0; }