C++学习——哈希表（一）

---

前言

本文为《C++学习》的第11篇文章，今天学习最后一个数据结构哈希表（散列表）。

---

一、哈希表的模板代码

#include<iostream>
using namespace std;// 哈希表节点模板类（链地址法实现）
template<typename KeyType, typename ValueType>
class HashNode {
public:KeyType key;            // 键（支持泛型）ValueType value;        // 值（支持泛型）HashNode *next;         // 指向下一个节点的指针// 构造函数（初始化键值对）HashNode(const KeyType &key, const ValueType &value) {this->key = key;this->value = value;this->next = nullptr;}
};// 哈希表模板类
template<typename KeyType, typename ValueType>
class HashTable {
private:int size;                            // 哈希表桶数量HashNode<KeyType, ValueType> **table;// 桶数组（指针数组）// 哈希函数（简单取模法，仅适合整数类型键）int hash(const KeyType &key) const {int hashkey = key % size;        // 核心哈希计算[3](@ref)if(hashkey < 0) hashkey += size; // 处理负数键return hashkey;}public:HashTable(int size = 256);          // 构造函数（默认桶数256）~HashTable();                       // 析构函数（释放内存）void insert(const KeyType &key, const ValueType &value); // 插入键值对void remove(const KeyType &key);    // 删除键bool find(const KeyType &key, ValueType &value) const; // 查找键
};/* 构造函数：初始化桶数组 */
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size;this->table = new HashNode<KeyType, ValueType> *[size]; // 动态分配桶数组for(int i = 0; i < size; ++i) {this->table[i] = nullptr; // 初始化所有桶为空}
}/* 析构函数：释放所有节点内存 */
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {for(int i = 0; i < size; ++i) {HashNode<KeyType, ValueType> *current = table[i];while(current) { // 遍历链表释放节点HashNode<KeyType, ValueType> *next = current->next;delete current; // 释放当前节点current = next;}}delete[] table; // 修正：需用delete[]释放数组[1](@ref)
}/* 插入操作（头插法，时间复杂度O(1)） */
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType &key, const ValueType &value) {int index = hash(key); // 计算桶索引HashNode<KeyType, ValueType> *newNode = new HashNode<KeyType, ValueType>(key, value);// 头插法插入链表newNode->next = table[index]; // 新节点指向原链表头table[index] = newNode;        // 更新链表头为新节点[3](@ref)
}/* 删除操作（需处理头节点和中间节点） */
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType &key) {int index = hash(key);if (!table[index]) return; // 空桶直接返回// 情况1：删除头节点if (table[index]->key == key) {HashNode<KeyType, ValueType> *temp = table[index];table[index] = table[index]->next; // 头节点指向下一个节点delete temp;return;}// 情况2：删除中间节点HashNode<KeyType, ValueType> *current = table[index];while (current->next && current->next->key != key) {current = current->next;}if (current->next) { // 找到目标节点HashNode<KeyType, ValueType> *temp = current->next;current->next = temp->next; // 跳过被删除节点delete temp;}
}/* 查找操作（遍历链表） */
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType &key, ValueType &value) const {int index = hash(key);HashNode<KeyType, ValueType> *current = table[index];while (current) {if (current->key == key) {value = current->value; // 返回找到的值return true;            }current = current->next;}return false; // 未找到返回false
}int main() {// 测试1：基础功能测试（整数键）HashTable<int, string> ht(10); // 桶数设为10便于观察冲突// 插入测试ht.insert(1, "Apple");ht.insert(11, "Banana"); // 与1同桶（哈希冲突）ht.insert(21, "Orange"); // 继续冲突ht.insert(5, "Grape");// 查找测试string value;cout << "--- 查找测试 ---" << endl;cout << "查找1: " << (ht.find(1, value) ? value : "Not Found") << endl; // Applecout << "查找11: " << (ht.find(11, value) ? value : "Not Found") << endl; // Bananacout << "查找99: " << (ht.find(99, value) ? value : "Not Found") << endl; // Not Found// 删除测试cout << "\n--- 删除测试 ---" << endl;ht.remove(11);cout << "删除后查找11: " << (ht.find(11, value) ? value : "Not Found") << endl; // Not Foundht.remove(1);cout << "删除头节点后查找1: " << (ht.find(1, value) ? value : "Not Found") << endl; // Not Foundcout << "删除后查找21: " << (ht.find(21, value) ? value : "Not Found") << endl; // Orange（验证链表连接正确性）// 测试2：模板类型测试（字符串键需自定义哈希函数，此处需改进）// HashTable<string, int> strHT; // 当前哈希函数仅支持整数，需扩展// 测试3：性能测试（插入1000个元素）HashTable<int, int> perfHT;for (int i = 0; i < 1000; ++i) {perfHT.insert(i, i*10);}int foundCount = 0;for (int i = 0; i < 1000; ++i) {int val;if (perfHT.find(i, val)) foundCount++;}cout << "\n--- 性能测试 ---\n成功查找次数: " << foundCount << "/1000" << endl;return 0; 
}

二、哈希计数器

#include<iostream>
#include<string>using namespace std;// 哈希表节点模板类（链地址法实现）
template<typename KeyType, typename ValueType>
class HashNode {
public:KeyType key;            // 键（支持泛型）ValueType value;        // 值（支持泛型）HashNode *next;         // 指向下一个节点的指针// 构造函数（初始化键值对）HashNode(const KeyType &key, const ValueType &value) {this->key = key;this->value = value;this->next = nullptr;}
};// 哈希表模板类
template<typename KeyType, typename ValueType>
class HashTable {
private:int size;                            // 哈希表桶数量HashNode<KeyType, ValueType> **table;// 桶数组（指针数组）// 哈希函数（简单取模法，仅适合整数类型键）int hash(const KeyType &key) const {int hashkey = key % size;        // 核心哈希计算[3](@ref)if(hashkey < 0) hashkey += size; // 处理负数键return hashkey;}public:HashTable(int size = 256);          // 构造函数（默认桶数256）~HashTable();                       // 析构函数（释放内存）void insert(const KeyType &key, const ValueType &value); // 插入键值对void remove(const KeyType &key);    // 删除键bool find(const KeyType &key, ValueType &value) const; // 查找键
};/* 构造函数：初始化桶数组 */
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size;this->table = new HashNode<KeyType, ValueType> *[size]; // 动态分配桶数组for(int i = 0; i < size; ++i) {this->table[i] = nullptr; // 初始化所有桶为空}
}/* 析构函数：释放所有节点内存 */
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {for(int i = 0; i < size; ++i) {HashNode<KeyType, ValueType> *current = table[i];while(current) { // 遍历链表释放节点HashNode<KeyType, ValueType> *next = current->next;delete current; // 释放当前节点current = next;}}delete[] table; // 修正：需用delete[]释放数组[1](@ref)
}/* 插入操作（头插法，时间复杂度O(1)） */
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType &key, const ValueType &value) {int index = hash(key); // 计算桶索引HashNode<KeyType, ValueType> *newNode = new HashNode<KeyType, ValueType>(key, value);// 头插法插入链表newNode->next = table[index]; // 新节点指向原链表头table[index] = newNode;        // 更新链表头为新节点[3](@ref)
}/* 删除操作（需处理头节点和中间节点） */
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType &key) {int index = hash(key);if (!table[index]) return; // 空桶直接返回// 情况1：删除头节点if (table[index]->key == key) {HashNode<KeyType, ValueType> *temp = table[index];table[index] = table[index]->next; // 头节点指向下一个节点delete temp;return;}// 情况2：删除中间节点HashNode<KeyType, ValueType> *current = table[index];while (current->next && current->next->key != key) {current = current->next;}if (current->next) { // 找到目标节点HashNode<KeyType, ValueType> *temp = current->next;current->next = temp->next; // 跳过被删除节点delete temp;}
}/* 查找操作（遍历链表） */
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType &key, ValueType &value) const {int index = hash(key);HashNode<KeyType, ValueType> *current = table[index];while (current) {if (current->key == key) {value = current->value; // 返回找到的值return true;            }current = current->next;}return false; // 未找到返回false
}/* 哈希计数器模板类* 功能：统计任意类型键的出现次数* 实现原理：*   1. 内部维护一个哈希表，映射键到计数数组索引*   2. 计数数组存储实际计数值*   3. 链地址法处理哈希冲突 */
template<typename KeyType>
class HashCounter {
private:int *counter;           // 计数数组，存储每个键的计数值int counterIndex;        // 当前可分配的计数数组索引int counterSize;         // 计数数组容量（最大唯一键数）HashTable<KeyType, int> *hash; // 哈希表，用于键到索引的映射public:/* 构造函数* @param size 最大支持的不同键数量 */HashCounter(int size = 256);/* 析构函数：释放动态内存 */~HashCounter();/* 重置所有计数和映射关系 */void reset();/* 增加键的计数（若不存在则创建）* @return 更新后的计数值 */int add(const KeyType &key);/* 减少键的计数（最小为0）* @return 更新后的计数值 */int sub(const KeyType &key);/* 获取键的当前计数 */int get(const KeyType &key);
};// 构造函数：初始化计数数组和哈希表
template<typename KeyType>
HashCounter<KeyType>::HashCounter(int size) {counterSize = size;counterIndex = 0;counter = new int[counterSize](); // 动态分配并初始化为0hash = new HashTable<KeyType, int>(size); // 哈希表容量与计数数组一致
}// 析构函数：释放内存
template<typename KeyType>
HashCounter<KeyType>::~HashCounter() {delete[] counter;  // 释放计数数组delete hash;        // 正确释放哈希表（非数组）
}// 重置所有计数状态
template<typename KeyType>
void HashCounter<KeyType>::reset() {delete hash; // 释放旧哈希表hash = new HashTable<KeyType, int>(counterSize); // 新建空哈希表counterIndex = 0;fill_n(counter, counterSize, 0); // 计数数组清零
}// 增加键的计数（自动处理新键）
template<typename KeyType>
int HashCounter<KeyType>::add(const KeyType &key) {int idx;if (!hash->find(key, idx)) {   // 新键处理if (counterIndex >= counterSize) { // 容量溢出保护cerr << "Error: Counter overflow! Max size: " << counterSize << endl;return -1;}idx = counterIndex++;hash->insert(key, idx);    // 插入新键与索引}return ++counter[idx];         // 计数+1并返回
}// 减少键的计数（最小为0）
template<typename KeyType>
int HashCounter<KeyType>::sub(const KeyType &key) {int idx;if (hash->find(key, idx)) {     // 仅处理已存在键if (counter[idx] > 0) {return --counter[idx];  // 计数-1}}return 0;
}// 获取键的当前计数
template<typename KeyType>
int HashCounter<KeyType>::get(const KeyType &key) {int idx;return (hash->find(key, idx)) ? counter[idx] : 0;
}int main() {// 初始化哈希表（桶数设为7便于观察冲突）HashTable<int, string> ht(7);string value; cout << "===== 测试1：基础插入与查找 =====" << endl;ht.insert(101, "Alice");ht.insert(202, "Bob");cout << "Key 101 -> " << (ht.find(101, value) ? value : "Not Found") << endl; // Alicecout << "Key 999 -> " << (ht.find(999, value) ? value : "Not Found") << endl; // Not Foundcout << "\n===== 测试2：键值更新 =====" << endl;ht.insert(202, "Bobby");  // 更新已有键ht.find(202, value);cout << "Key 202 -> " << value << endl; // Bobbycout << "\n===== 测试3：哈希冲突处理 =====" << endl;ht.insert(7, "Conflict1");  // 7 % 7 = 0ht.insert(14, "Conflict2"); // 14 % 7 = 0cout << "Bucket 0 查找测试：" << endl;cout << "Key 7 -> " << (ht.find(7, value) ? value : "Not Found") << endl;    // Conflict1cout << "Key 14 -> " << (ht.find(14, value) ? value : "Not Found") << endl;  // Conflict2cout << "\n===== 测试4：删除操作 =====" << endl;ht.remove(202);cout << "删除后查找202 -> " << (ht.find(202, value) ? value : "Not Found") << endl; // Not Foundcout << "\n===== 测试5：负数键处理 =====" << endl;ht.insert(-5, "Negative");  // (-5 % 7 + 7) = 2cout << "Key -5 -> " << (ht.find(-5, value) ? value : "Not Found") << endl;  // Negativereturn 0;
}

---

三、哈希表中的无序映射

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;int main() {// 初始化无序映射容器unordered_map<string, int> student_scores;/****************** 插入操作 ******************/// 方法1: 使用 operator[] 插入新键值对（若键存在则覆盖）student_scores["Alice"] = 90;   // 插入 Alice:90student_scores["Bob"] = 85;     // 插入 Bob:85// 方法2: 使用 insert 插入（若键存在则不会覆盖）student_scores.insert({"Charlie", 88});  // 插入 Charlie:88student_scores.insert(make_pair("David", 92)); // 插入 David:92// 方法3: 使用 emplace 高效插入（C++11特性）student_scores.emplace("Eva", 95);  // 插入 Eva:95/****************** 查询操作 ******************/// 方法1: 使用 operator[] 查询（若键不存在会创建默认值）cout << "Alice's score: " << student_scores["Alice"] << endl; // 输出90// 方法2: 使用 find 安全查询（推荐）auto it = student_scores.find("Bob");if (it != student_scores.end()) {cout << "Bob's score: " << it->second << endl;  // 输出85} else {cout << "Bob not found" << endl;}// 方法3: 使用 count 检查键是否存在if (student_scores.count("Charlie")) {cout << "Charlie exists" << endl;  // 输出存在}/****************** 修改操作 ******************/// 方法1: 通过 operator[] 直接修改student_scores["Alice"] = 95;  // Alice成绩修改为95// 方法2: 通过迭代器修改（需先查找）auto update_it = student_scores.find("David");if (update_it != student_scores.end()) {update_it->second = 100;  // David成绩修改为100}/****************** 删除操作 ******************/// 方法1: 通过键删除student_scores.erase("Eva");  // 删除Eva记录// 方法2: 通过迭代器删除auto del_it = student_scores.find("Charlie");if (del_it != student_scores.end()) {student_scores.erase(del_it);  // 删除Charlie记录}/****************** 遍历操作 ******************/cout << "\nFinal scores:" << endl;for (const auto& pair : student_scores) {  // 范围for遍历cout << pair.first << ": " << pair.second << endl;}// 方法2: 使用迭代器遍历cout << "\nIterator traversal:" << endl;for (auto it = student_scores.begin(); it != student_scores.end(); ++it) {cout << it->first << " => " << it->second << endl;}/****************** 清空容器 ******************/student_scores.clear();cout << "\nAfter clear, size: " << student_scores.size() << endl;return 0;
}

---

四、哈希表的总结

---

这就是今天的全部内容了，谢谢大家的观看，不要忘了给一个免费的赞哦！