手动实现哈希表主要用于教学、面试、嵌入式或需精细控制哈希策略/内存布局/冲突处理；常见选择为线性探测（开放寻址）或拉链法，需关注负载因子扩容、删除标记、哈希均匀性及边界安全。
为什么不用 std::unordered_map 而要手动实现
通常是因为教学、面试、嵌入式环境限制，或需要完全控制哈希策略、内存布局、冲突处理方式。手动实现能暴露关键设计点：哈希函数选择、桶数组大小、开放寻址 vs 链地址法、扩容时机与方式。注意：std::unordered_map 默认用链地址法 + 素数桶数 + 二次哈希，而手写常选更易理解的线性探测（开放寻址）或简单拉链法。
用线性探测实现插入和查找（C++11+）
线性探测简单直观，但容易聚集；适合教学和小规模数据。核心是：计算 hash(key) % bucket_size 得到初始位置，冲突时顺序往后找空位或匹配键。
- 哈希函数建议用
std::hash<key>()(key)</key>，避免自己写低质量散列 - 桶数组用
std::vector<:pair value>></:pair>，空位用特殊标记（如std::optional或布尔数组标记有效位） - 删除操作不能真删，需设为“已删除”状态（
deleted），否则会断开后续查找链 - 负载因子超过 0.7 就该扩容——重新分配更大桶数组，再逐个
rehash插入
template<typename Key, typename Value>
class SimpleHashMap {
struct Entry {
std::optional<std::pair<Key, Value>> data;
bool deleted = false;
};
std::vector<Entry> buckets;
size_t size_ = 0;
static constexpr float MAX_LOAD_FACTOR = 0.7f;
<pre class='brush:php;toolbar:false;'>size_t hash(const Key& k) const {
return std::hash<Key>{}(k) & (buckets.size() - 1); // 要求 bucket_size 是 2 的幂
}public:
void insert(const Key& k, const Value& v) {
if (staticcast
size_t idx = hash(k);
while (buckets[idx].data.has_value() && !buckets[idx].deleted) {
if (buckets[idx].data->first == k) {
buckets[idx].data->second = v; // 更新
return;
}
idx = (idx + 1) & (buckets.size() - 1); // 线性探测，要求 size 是 2 的幂
}
buckets[idx].data = std::make_pair(k, v);
buckets[idx].deleted = false;
++size_;
}
Value* find(const Key& k) {
size_t idx = hash(k);
while (buckets[idx].data.has_value()) {
if (!buckets[idx].deleted && buckets[idx].data->first == k)
return &buckets[idx].data->second;
idx = (idx + 1) & (buckets.size() - 1);
}
return nullptr;
}private:
void rehash(size_t new_size) {
std::vector
拉链法实现更简洁但指针管理要小心
每个桶存一个 std::vector 或 std::list，插入即 push_back，查找遍历桶内链表。优势是删除干净、逻辑清晰；劣势是额外指针开销、缓存不友好。
- 不要用裸指针管理节点，优先用
std::vector<:pair value>></:pair>存桶，避免内存泄漏 - 桶数组大小建议用素数（如 31、101、1009），减少哈希分布偏斜；可用静态素数表或运行时计算
- 查找时仍要遍历桶内所有元素，最坏 O(n)，但平均 O(1) —— 前提是哈希函数够均匀
常见崩溃和未定义行为点
手动实现哈希表最容易栽在边界和状态管理上：
立即学习“C++免费学习笔记（深入）”；
-
hash(key) % bucket_size中若bucket_size == 0（初始化没做），会触发除零错误 - 没处理自赋值或移动语义，
insert(k, std::move(v))后又访问v导致悬垂引用 - 扩容时没正确处理
deleted标记，导致旧数据被跳过或重复插入 - 用
std::string或自定义类型作 key 时，忘了重载operator==或提供等价比较谓词，find永远失败 - 多线程环境下未加锁，
insert和find并发引发数据竞争
真正难的不是写完，而是让 erase、clear、迭代器、异常安全、移动构造这些边缘操作都稳住——多数人卡在这一步就退回 std::unordered_map 了。
