本文介绍了哈希表的基本概念、负载因子、哈希冲突及解决方法（线性探测、哈希桶）。详细讲解了哈希函数的设计原则，并分别使用线性探测法和哈希桶法模拟实现了哈希表类。最后基于哈希桶结构，引入迭代器，模拟实现了 C++ STL 中的 unordered_map 和 unordered_set，包含完整的代码示例与测试验证。
什么是哈希表？
哈希表是一种通过键（Key）来直接访问值（Value）的数据结构，它利用一个叫做哈希函数的公式，把任意大小的键转换成一个固定大小的数字，这个数字被称为或。然后，用这个哈希值作为数组的，将值存储在这个索引对应的数组位置上。
哈希表的本质是一个数组
哈希表本质上是一个基于数组实现的数据结构，其核心设计思想是利用数组的随机访问特性，实现快速的插入、删除和查找操作。
具体来说，它通过一个哈希函数将键映射为一个整数值，这个值经过处理（通常是对数组长度取模）后，作为该键值对在数组中的存储下标。
理想情况下，每个键都能通过哈希函数得到一个唯一的、不冲突的下标，这样我们就可以直接将值存放到数组的对应位置，访问时也能立刻定位——时间复杂度接近 O(1)。
然而，现实应用中，哈希函数很难做到为所有可能的键生成独一无二的索引。因为键的空间通常远大于数组的容量，所以不同的键有可能计算出相同的数组下标，这就是所谓的哈希冲突。
常见的冲突解决方法有两种：
HashMap 就采用这种思路。为了保持高效，哈希表还需要动态调整大小。通常会设定一个负载因子阈值，当元素数量与数组长度的比值超过该阈值时，就对数组进行扩容，将容量扩大，并将所有现有元素重新哈希到新数组中。
核心组件
一个哈希表主要由以下三个核心部分组成：
哈希表的效率高度依赖于一个关键指标：负载因子。
负载因子 = 哈希表中已存储的元素数量 / 哈希表数组的总大小
为了保持高性能，当负载因子超过某个阈值（例如 0.75）时，哈希表会进行扩容操作：创建一个新的更大的数组，遍历旧哈希表中的所有键值对，根据新的数组大小重新计算索引并插入。
这个过程称为 Rehashing，虽然耗时，但能显著降低负载因子，使哈希表恢复高效。
哈希冲突，简单来说，就是两个不同的输入值，经过同一个哈希函数计算后，得到了相同的输出值。
从数学上讲，哈希函数是一个压缩映射，它的输出空间通常远小于输入空间。根据鸽巢原理，当输入数量超过输出数量时，必然存在至少一个输出值对应多个输入值。
哈希函数负责将关键码（Key）映射为一个数组下标（哈希地址）。
一个好的哈希函数应当满足以下原则：
1. 直接定址法
公式：Hash(Key) = A * Key + B
直接使用关键码本身（或它的线性变换）作为哈希地址。适用于关键码是整数且取值范围较小且连续的情况。
2. 除留余数法
公式：Hash(Key) = Key % p
其中 p 是一个不大于哈希表长度 m 的质数。这种方法能将任意整数关键码压缩到 0 ~ p-1 的范围内。
我们来深入探讨哈希冲突解决的两种常用方法：线性探测法和哈希桶（即链地址法）。
使用开放地址法中的线性探测法，需要借助状态标记。
首先，要实现哈希表，我们得定义出一些东西出来：
// 哈希表中每个位置的状态标记
enum STATE {
EXIST, // 当前位置有有效数据
EMPTY, // 当前位置为空
DELETE // 当前位置的数据已被删除（逻辑删除）
};
// 哈希表存储的数据节点结构
template<class K, class V>
struct HashData {
pair<K, V> _kv; // 存储的键值对
STATE _state = EMPTY; // 当前节点的状态，默认为空
};
我们需要定义哈希函数对象。对于不同类型（如整数、字符串），可以使用模板特化。
// 默认的哈希函数对象（适用于整数等可直接转换为 size_t 的类型）
template<class K>
struct DefaultHashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
// 对 string 类型的特化哈希函数（使用 BKDR 算法）
template<>
struct DefaultHashFunc<string> {
size_t operator()(const string& str) {
size_t hash = 0;
for (auto ch : str) {
hash *= 131;
hash += ch;
}
return hash;
}
};
// 哈希表类，使用开放地址法（线性探测）解决冲突
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
public:
// 构造函数：初始化哈希表大小（默认 10）
HashTable() {
_table.resize(10);
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0; // 当前哈希表中有效数据的个数
};
整个插入操作分为两步：判断是否需要扩容，以及通过线性探测法插入新元素。
bool Insert(const pair<K, V>& kv) {
// 扩容判断：负载因子 >= 0.7 时扩容
if (_n * 10 / _table.size() >= 7) {
size_t newSize = _table.size() * 2;
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
// 遍历旧表，将所有状态为 EXIST 的节点重新插入到新表
for (size_t i = 0; i < _table.size(); i++) {
if (_table[i]._state == EXIST) {
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
// 线性探测法寻找插入位置
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST) {
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY) {
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
return (HashData<const K, V>*)&_table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key) {
HashData<const K, V>* ret = Find(key);
if (ret) {
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
（此处省略完整的头文件 test.cpp 代码展示，主要包含插入、查找、删除及扩容测试逻辑）
哈希桶（Hash Bucket）就是链地址法的一种实现方式。每个桶对应一个链表，所有映射到同一索引的键值对都存储在这个桶所指向的链表中。
复用之前的哈希函数定义。
template <class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
public:
HashTable() {
_table.resize(10, nullptr);
}
~HashTable() {
for (size_t i = 0; i < _table.size(); i++) {
Node *cur = _table[i];
while (cur) {
Node *next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
// ... 其他成员函数
private:
vector<Node *> _table;
size_t _n = 0;
};
bool Insert(const pair<K, V> &kv) {
if (Find(kv.first)) {
return false;
}
HashFunc hf;
// 扩容：当负载因子达到 1 时，将桶数组大小扩大为原来的 2 倍
if (_n == _table.size()) {
size_t newSize = _table.size() * 2;
vector<Node *> newTable;
newTable.resize(newSize, nullptr);
// 遍历旧表，将每个节点重新哈希并头插到新表
for (size_t i = 0; i < _table.size(); i++) {
Node *cur = _table[i];
while (cur) {
Node *next = cur->_next;
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kv.first) % _table.size();
Node *newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
Node *Find(const K &key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node *cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K &key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node *prev = nullptr;
Node *cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) {
_table[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
（包含完整的 HashTable.hpp 和 test.cpp 实现，支持整型和字符串类型测试）
C++ STL 库里面的 unordered_map 和 unordered_set 的底层实现都是基于哈希表来模拟实现的。
这段代码实现了一个哈希表的正向迭代器，支持普通迭代器和 const 迭代器。
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
// ... 构造函数及运算符重载
};
引入迭代器后，需要修改哈希表类以支持 begin() 和 end() 接口，并修改 Insert 返回值为 pair<iterator, bool>。
namespace mySTL {
template<class K, class V>
class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<const K, V>& kv) {
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }
pair<iterator, bool> insert(const pair<K, V>& kv) {
return _ht.Insert(kv);
}
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}
namespace mySTL {
template<class K>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) {
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
pair<iterator, bool> insert(const K& key) {
pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}
（测试程序验证了插入、查找、删除及迭代器遍历功能）
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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