C++简易哈希表基于vector+list实现链地址法，支持int→string映射；核心包括取模哈希函数、桶内查重更新、引用返回查找值、迭代器删除；代码完整可运行，涵盖插入、查找、删除操作。
用C++实现一个简单的哈希表，核心是解决两个问题：哈希函数计算键的索引，以及处理哈希冲突（最常用的是链地址法）。下面是一个基于std::vector + std::list的简易开放寻址式哈希表（简化版，无动态扩容），支持插入、查找和删除。
哈希函数与桶结构设计
选择简单但分布较均匀的哈希函数（如对整数直接取模），用std::vector存储多个桶（每个桶是std::list<std::pair<Key, Value>>），避免指针管理复杂度。
- 哈希函数：对键取模桶数量，例如
hash(key) = std::abs(static_cast<int>(key)) % buckets.size() - 桶类型：每个桶存一个链表，容纳冲突的键值对
- 不支持泛型键类型（本例以
int为键，std::string为值）便于理解；实际可模板化
完整可运行代码（C++11及以上）
// 简单哈希表实现：支持 int → string 映射
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <cmath>
#include <algorithm>
class SimpleHashTable {
private:
static const size_t INITIAL_BUCKETS = 10;
std::vector<std::list<std::pair<int, std::string>>> buckets;
size_t hash(int key) const {
return std::abs(key) % buckets.size();
}
public:
SimpleHashTable() : buckets(INITIAL_BUCKETS) {}
void insert(int key, const std::string& value) {
size_t idx = hash(key);
auto& bucket = buckets[idx];
// 先尝试更新已存在键
for (auto& pair : bucket) {
if (pair.first == key) {
pair.second = value;
return;
}
}
// 否则插入新节点
bucket.emplace_back(key, value);
}
bool find(int key, std::string& out_value) const {
size_t idx = hash(key);
const auto& bucket = buckets[idx];
for (const auto& pair : bucket) {
if (pair.first == key) {
out_value = pair.second;
return true;
}
}
return false;
}
bool erase(int key) {
size_t idx = hash(key);
auto& bucket = buckets[idx];
for (auto it = bucket.begin(); it != bucket.end(); ++it) {
if (it->first == key) {
bucket.erase(it);
return true;
}
}
return false;
}
};
// 使用示例
int main() {
SimpleHashTable ht;
ht.insert(10, "apple");
ht.insert(20, "banana");
ht.insert(105, "cherry"); // 105 % 10 = 5，与 20 不冲突（20%10=0）
std::string val;
if (ht.find(10, val)) std::cout << "10 → " << val << "\n"; // apple
if (ht.find(20, val)) std::cout << "20 → " << val << "\n"; // banana
if (!ht.find(99, val)) std::cout << "99 not found\n";
ht.erase(10);
if (!ht.find(10, val)) std::cout << "10 removed\n";
}
关键细节说明
哈希冲突处理：采用链地址法（separate chaining），每个桶是链表，插入/查找/删除都在对应链表内操作，逻辑清晰且易于实现。
立即学习“C++免费学习笔记（深入）”；
- 插入时先查重再更新，避免重复键
- 查找失败返回
false，成功通过引用输出值 - 删除使用迭代器遍历并擦除，注意及时返回避免越界
可改进点（进阶参考）：
- 添加模板支持任意
Key和Value类型（需提供std::hash<T>或自定义哈希） - 实现负载因子监控和自动扩容（如当平均链长 > 1.5 时重建桶数组）
- 改用开放寻址（线性探测/二次探测），节省内存但删除更复杂
不复杂但容易忽略
哈希表不是“一写就完”，真正实用的版本需要考虑：键的可哈希性、空值处理、异常安全、迭代器支持。但这个基础版本已涵盖核心机制——哈希定位 + 冲突应对。动手写一遍，比看十篇理论更能理解它怎么工作。
