C++算法
C++ Unordered 系列容器及哈希表底层原理实现
C++11 引入 unordered 系列容器，底层基于哈希表实现 O(1) 查询效率。模拟实现了 HashBucket、UnorderedMap 和 UnorderedSet，详细讲解了哈希冲突解决（开散列/链地址法）、节点设计、扩容机制及迭代器实现。通过模板特化支持 string 作为 Key，并封装了 Map 的 [] 运算符重载逻辑。
C++11 引入 unordered 系列容器，底层基于哈希表实现 O(1) 查询效率。模拟实现了 HashBucket、UnorderedMap 和 UnorderedSet，详细讲解了哈希冲突解决（开散列/链地址法）、节点设计、扩容机制及迭代器实现。通过模板特化支持 string 作为 Key，并封装了 Map 的 [] 运算符重载逻辑。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
在 C++98 中，STL 提供了底层为红黑树的关联式容器（map/set），查询效率为 O(logN)。为了追求极致的查找速度，C++11 引入了 unordered 系列容器，其底层采用哈希表结构，理论上查询效率可达到 O(1)。
本文将模拟实现代码（HashBucket, UnorderedMap, UnorderedSet），深入剖析其底层原理与实现细节。
哈希（Hash）通过一个哈希函数（HashFunc），将元素的关键码（Key）映射到存储位置，建立一一映射关系，从而实现不经过比较直接查找元素。
公式：hash(key) = key % capacity
当不同的关键字通过哈希函数计算出相同的哈希地址时，就会发生哈希冲突（Hash Collision）。解决冲突主要有两种方式：
当发生冲突时，如果哈希表未满，将 key 存放到冲突位置的'下一个'空位置。
线性探测：挨个往后找。容易产生'数据堆积'。
二次探测：通过跳转查找，缓解堆积。
这是 STL unordered_map 通常采用的方法，也是我们代码中实现的方法。
原理：将具有相同哈希地址的元素归于同一子集合（桶），每个桶通过单链表链接。哈希表中存储的是链表的头指针。
我们在 HashBucket.h 中实现了开散列的哈希表。
使用模板结构体 HashNode，存储数据和下一个节点的指针。
template <class T>
struct HashNode {
T _data;
HashNode* _next;
// ... 构造函数
};
为了支持 string 作为 Key，我们需要对哈希函数进行特化。代码中使用了类似 BKDRHash 的思路（乘数为 31）将字符串转化为整型。
template <>
struct HashFunc<string> {
const int operator()(const string& str) {
int hashi = 0;
for (int i = 0; i < str.size(); i++) {
hashi += str[i];
hashi *= 31; // 经典乘数，减少冲突
}
return hashi;
}
};
插入 (Insert)：
index，将新节点插入到 _table[index] 的头部（效率最高）。复用节点：
在扩容时，代码没有创建新节点，而是直接将旧表的节点'搬运'到新表，节省了 new 和 delete 的开销。
if (_n == _table.size()) {
vector<Node*> newHt;
newHt.resize(_n * 2);
// 遍历旧表，重新计算 hash 值挂到新表
// ...
_table.swap(newHt);
}
unordered 容器的迭代器是单向迭代器（Forward Iterator）。
结构：迭代器需要持有 Node*（当前节点）和 HashBucket*（哈希表指针）。
operator++ 实现逻辑：
_node->_next != nullptr)，则指向下一个节点。_ht 指针计算当前桶的下标，并在哈希表中向后寻找第一个非空的桶。为了复用同一份 HashBucket 代码，我们利用模板参数采用了类似适配器模式的设计。
HashBucket 存储的是 T，但不知道 T 中哪个部分是 Key。
T 就是 K。SetOfT 仿函数直接返回 Key。pair<K, V>。MapOfT 仿函数返回 pair.first。map 的 [] 运算符非常强大：如果 Key 存在则查找，不存在则插入默认值。
实现逻辑是调用 Insert，利用其返回值 pair<iterator, bool> 来获取 Value 的引用。
V& operator[](const K& key) {
auto it = Insert(make_pair(key, V())).first;
return (*it).second;
}
以上就是对哈希相关内容的总结了。