1 哈希表的概念
1.1 哈希的含义
哈希（又称散列），是一种通过哈希函数来得到值与存储位置的映射关系的存储方式。
C++算法
哈希表原理与实现：线性探测及链地址法
哈希表通过哈希函数建立键值与存储位置的映射。哈希含义、冲突概念及负载因子，阐述了直接定址、除法散列、乘法散列等映射方法。重点讲解了开放定址法（线性探测、二次探测）和链地址法两种冲突解决策略，并提供了基于 C++ 模板的线性探测与链地址法完整代码实现，包含查找、插入、删除及扩容逻辑。
哈希表通过哈希函数建立键值与存储位置的映射。哈希含义、冲突概念及负载因子，阐述了直接定址、除法散列、乘法散列等映射方法。重点讲解了开放定址法（线性探测、二次探测）和链地址法两种冲突解决策略，并提供了基于 C++ 模板的线性探测与链地址法完整代码实现，包含查找、插入、删除及扩容逻辑。
哈希（又称散列），是一种通过哈希函数来得到值与存储位置的映射关系的存储方式。
哈希冲突指在使用哈希函数存储元素时，多个元素通过哈希函数计算得到的映射位置是一样的，此时它们就会争夺同一个存储位置。这种现象叫做哈希冲突，哈希冲突是不可避免的，但可以通过设计出好的哈希函数来减少冲突。
例如 x、y、z 通过哈希函数得到的映射位置都是 3，此时相当于它们在争夺这个存储位置，发生了哈希冲突。
负载因子指哈希表内元素的占比。假设存储的元素个数为 N，哈希表长度为 M，负载因子为 N/M。负载因子越大，说明存储的元素越多，发生哈希冲突的概率越大，空间利用率越高；负载因子越小，说明存储的元素越少，发生哈希冲突的概率越小，空间利用率越低。
例如下图中哈希表的负载因子就等于 8 / 11 = 0.73。
直接定址法直接用元素的值充当存储位置来进行映射。比如下标为 [0, 10] 的数组，用直接定址法来做映射，那么 0 直接映射到下标为 0 的存储位置上，1 直接映射到下标为 1 的存储位置上。
直接定址法只适合用于元素之间的值相差不大的情况。如果有一组数据，它里面元素的值相差过大，那么使用直接定址法会导致空间浪费。比如要存储 [0, 9999]，虽然只有两个值但是要开辟 10000 个空间来存储，造成了很大的空间浪费，此时通过哈希函数来获得新的映射方案会更理想。
除法散列法是通过取模的方式来获取余数，以该余数作为映射位置的一种映射方案。假设哈希表长度为 M，元素的值为 key，那么最终得到的映射位置：h(key) = key % M。
在使用除法散列法时，哈希表长度建议取不接近 2 的整数次幂的质数。
假设哈希表长 M 为 7，要映射的值 key 为 5，那么根据除留余数法最终可以得到映射的下标是 5 % 7 = 5。
乘法散列法的思想是用元素的值 key 先乘上小数 A (0<A<1)，再 %1.0 获得结果的小数部分，最后让 M 乘上这个小数部分，向下取整来得到映射位置 h(key) = floor(M * ((key * A) % 1.0))。floor 为向下取整，A 一般取 0.6180339887。
假设哈希表长 M 为 1024，key 为 1234，A = 0.6180339887，A * key = 762.6539420558，% 1.0 取小数部分 0.6539420558，乘以表长 1024 * 0.6539420558 = 669.6366651392，向下取整最终得到 669，也就是映射的位置。
如果哈希函数是固定不变的，此时可能会出现有人设计了一组数据，将这组数据通过已设计好的哈希函数进行存储，让数据都存储到一个位置上，发生多次哈希冲突，以此来降低效率。全域散列法就是为了解决这种问题存在的。
全域散列法的映射方案为 h(key) = ((a * key + b) % P) % M。P 为一个较大的质数，a 在 [1, P-1] 范围内随机选取一个值，b 在 [0, P-1] 范围内随机选取一个值，这样就能得到 (P - 1) * P 个哈希函数，在初始化哈希表时，随机选取其中的一个进行使用。
线性探测法的思路为发生冲突时，从发生冲突的位置依次向后寻找，直到找到没有数据的位置为止，将元素存入该位置。如果遇到表尾，则回到表头继续查找。
使用 h(key) = key % M 得到第一次要映射的位置 hash0，若该位置发生哈希冲突，则使用 h(key) = (hash0 + i) % M 来查找下一个要映射的位置 hashi，i 的取值为 [1, M-1]。如果负载因子小于 1，最少留下一个位置可以用来存储，则最多探测 M - 1 次得到要映射的位置。
假设一个元素 x 要映射到位置 hash0 上但是发生冲突，那么它就会继续向后查找 hash1，hash2，hash3，最后它存放在了 hash3 的位置上。此时元素 y，z 到来，第一次分别映射到 hash1 和 hash2 的位置上，进行查找后，最后它们都会对 hash3 的位置进行争夺，这种现象叫做堆积（群聚）。
线性探测法例：将
[19, 30, 5, 36, 13, 20, 21, 12]这一组数据映射到长度 M 为 11 的哈希表中：
h(19) = 19 % 11 = 8
h(30) = 30 % 11 = 8 -> h(30) = (8 + 1) % 11 = 9
h(5) = 5 % 11 = 5
h(36) = 36 % 11 = 3
h(13) = 13 % 11 = 2
h(20) = 20 % 11 = 9 -> h(20) = (9 + 1) % 11 = 10
h(21) = 21 % 11 = 10 -> h(21) = (10 + 1) % 11 = 0
h(12) = 12 % 11 = 1
二次探测法的思路为发生冲突时，从发生冲突的位置依次向前向后寻找，直到找到没有数据的位置为止。
使用 h(key) = key % M 得到第一次要映射的位置 hash0，若该位置发生哈希冲突，则使用 h(key, i) = (hash0 + i^2) % M 或类似变体来查找下一个要映射的位置 hashi。通常 i 的取值为 [1^2, -(1)^2, 2^2, -(2)^2, …]。当 hashi < 0 时，要加上表长 M，否则无法存储。
二次探测法例：将
[19, 30, 52, 63, 11, 22]这一组数据映射到长度 M 为 11 的哈希表中：
h(19) = 19 % 11 = 8
h(30) = 30 % 11 = 8 -> h(30, 1) = (8 + 1) % 11 = 9
h(52) = 52 % 11 = 8 -> h(52, 1) = (8 + 1) % 11 = 9 -> h(52, -1) = (8 - 1) % 11 = 7
h(63) = 63 % 11 = 8 -> h(63, 1) = (8 + 1) % 11 = 9 -> h(63, -1) = (8 - 1) % 11 = 7 -> h(63, 4) = (8 + 4) % 11 = 1
h(11) = 11 % 11 = 0
h(22) = 22 % 11 = 0 -> h(22, 1) = (0 + 1) % 11 = 1 -> h(22, -1) = (0 - 1) % 11 = -1，再 -1 + 11 = 10
链地址法也叫哈希桶或拉链法。链地址法中，哈希表的每个位置上都有一个指针，当有元素映射到一个位置上时，就用该元素创建一个结点，挂到对应的指针上。当没有元素映射时，指针是空的。
链地址法例：将
[19,30,5,36,13,20,21,12,24,96]映射到长度 M = 11 的哈希表中：
19 % 11 = 8，30 % 11 = 8，5 % 11 = 5，36 % 11 = 3，13 % 11 = 2
20 % 11 = 9，21 % 11 = 10，12 % 11 = 1，24 % 11 = 2，96 % 11 = 8
主要用来表示哈希表中存储位置的状态。
enum State {
EXIST, // 表示有数据
EMPTY, // 表示无数据
DELETE // 表示数据已删除
};
template<class K, class V>
struct HashData {
pair<K, V> _data; // 数据
State _state; // 标识
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
// ...
private:
vector<HashData<K, V>> _table; // 存储数据的顺序表
size_t _n; // 有效元素个数
};
为了让负数、小数、字符串都可以被插入到哈希表中，需要把它们转化成整数。
负数、小数在转化时，要转化为 size_t 类型的数据，否则无法进行插入。
字符串在转化时，需要把每个字符的 ASCII 值相加，用最终的和来得到映射位置。但是像 "abc" 和 "bac" 这样的字符串，ASCII 值相加后值是一样的，为了防止这种问题，需要在每次加的时候乘以质数。
template<class K>
class HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
// 处理字符串的特化类
template<>
class HashFunc<string> {
size_t operator()(const string& str) {
size_t key = 0;
for (auto& e : str) {
key += e;
key *= 131;
}
return key;
}
};
先根据 h(key) = key % M 计算出 hash0，从 hash0 的位置开始进行查找。若该位置的状态为 EXIST（值存在）并且值等于 key，那么说明找到了需求的值，返回该值的地址。若该位置的状态为 DELETE（元素已删除）或存在值但是不相等，仍然需要向后进行查找。此时通过 h(key) = (hash0 + i) % M 的方式得到新的映射位置再与该位置上的值进行比较。若最后到 EMPTY 还没找到则说明哈希表内没有需求的值，返回空指针即可。
HashData<K, V>* Find(const K& key) {
Hash hash;
int hash0 = hash(key) % _table.size();
int hashi = hash0;
int i = 1;
while (_table[hashi]._state != EMPTY) {
if (_table[hashi]._state == EXIST && _table[hashi]._data.first == key) {
return &_table[hashi];
}
hashi = (hash0 + i) % _table.size();
i++;
}
return nullptr;
}
查找成功时：
查找失败时：
为了进行去重，先根据 key 查找元素是否在哈希表内。在哈希表内则不需要进行插入，不在则进行插入。插入前，先根据负载因子来判断是否进行扩容，负载因子 > 0.7 时进行扩容。扩容时定义新的哈希表，对函数 Insert 进行复用，将原表的值放入新表，再交换两个表即可。扩容完后进行插入，使用 h(key) = key % M 计算出 hash0，若 hash0 的位置已有元素（EXIST），则通过 h(key) = (hash0 + i) % M 继续向后查找，直到找到无元素的位置（DELETE 或 EMPTY），将值插入。
bool Insert(const pair<K, V>& kv) {
// 已有元素则不进行插入
if (Find(kv.first)) return false;
// 负载因子大于 0.7 进行扩容
if (_n * 10 / _table.size() >= 7) {
HashTable<K, V, Hash> newTable;
newTable._table.resize(__stl_next_prime(_table.size() + 1)); // +1 防止开的空间不变
// 将旧表数据放入新表
for (int i = 0; i < _table.size(); ++i) {
if (_table[i]._state == EXIST) {
newTable.Insert(_table[i]._data);
}
}
// 交换新表和旧表
swap(newTable._table, _table);
}
// 寻找位置插入
Hash hash;
int hash0 = hash(kv.first) % _table.size();
int hashi = hash0;
int i = 1;
while (_table[hashi]._state == EXIST) {
hashi = (hash0 + i) % _table.size();
i++;
}
_table[hashi]._data = kv;
_table[hashi]._state = EXIST;
_n++;
return true;
}
使用 key 先在表内进行查找，若找不到则不需要删除。若找得到则直接将状态设置为 DELETE，表示元素被删除。设置为 DELETE 的目的为防止删除元素后影响查找。
bool Erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (!ret) return false;
ret->_state = DELETE;
_n--;
return true;
}
不设置为 DELETE，删除后影响查找的情况：
由于 hash0 处被标记为了 EMPTY，所以查找时直接返回，但是 20 在该位置后面，所以查找结果出现了错误。
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& str) {
size_t key = 0;
for (auto& e : str) {
key += e;
key *= 131;
}
return key;
}
};
enum State {
EXIST, // 表示有数据
EMPTY, // 表示无数据
DELETE // 表示数据已删除
};
template<class K, class V>
struct HashData {
pair<K, V> _data; // 数据
State _state = EMPTY; // 标识
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
// C++ 库中使用的扩容方案 -- 列举出多个质数
inline unsigned long __stl_next_prime(unsigned long n) {
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
402653189, 805306457, 1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable() {
_table.resize(__stl_next_prime(0));
_n = 0;
}
bool Insert(const pair<K, V>& kv) {
// 已有元素则不进行插入
if (Find(kv.first)) return false;
// 负载因子大于 0.7 进行扩容
if (_n * 10 / _table.size() >= 7) {
HashTable<K, V, Hash> newTable;
newTable._table.resize(__stl_next_prime(_table.size() + 1)); // +1 防止开的空间不变
// 将旧表数据放入新表
for (int i = 0; i < _table.size(); ++i) {
if (_table[i]._state == EXIST) {
newTable.Insert(_table[i]._data);
}
}
// 交换新表和旧表
swap(newTable._table, _table);
}
// 寻找位置插入
Hash hash;
int hash0 = hash(kv.first) % _table.size();
int hashi = hash0;
int i = 1;
while (_table[hashi]._state == EXIST) {
hashi = (hash0 + i) % _table.size();
i++;
}
_table[hashi]._data = kv;
_table[hashi]._state = EXIST;
_n++;
return true;
}
HashData<K, V>* Find(const K& key) {
Hash hash;
int hash0 = hash(key) % _table.size();
int hashi = hash0;
int i = 1;
// 查找到空为止
while (_table[hashi]._state != EMPTY) {
// 若存在值并且相等，返回该值的地址
if (_table[hashi]._state == EXIST && _table[hashi]._data.first == key) {
return &_table[hashi];
}
// 若存在值不相等或值已删除，则继续向后查找
hashi = (hash0 + i) % _table.size();
i++;
}
return nullptr;
}
bool Erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (!ret) return false;
ret->_state = DELETE;
_n--;
return true;
}
private:
vector<HashData<K, V>> _table;
size_t _n;
};
链地址法中，仿函数 HashFunc，枚举类型 State 和线性探测法中一致。
由于链地址法中，哈希表的每一个位置上都是一个链表，所以就要开辟链表中的结点并将数据存放进去。
template<class K, class V>
struct HashNode {
HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
pair<K, V> _kv;
HashNode<K, V>* _next; // 指向下一结点的指针
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
public:
// ...
private:
vector<Node*> _table; // 使用 vector，因为 list 的迭代器不方便在这里使用
size_t _n; // 有效元素个数
};
由于哈希表中存了许多的结点，所以要释放掉这些结点。每一个哈希桶相当于是一个链表，对哈希桶按照链表的方式释放即可。定义 cur，删除 cur 前，先记录它的下一个节点 next，删除 cur 后，cur = next 向后移动。当 cur 为空时，说明当前的哈希桶删除完毕，把头结点指针置为空，移动到下一个哈希桶即可。
~HashTable() {
for (int i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
计算出元素要映射的位置 hashi，确定要查找的哈希桶，在该哈希桶内查找元素。找到了则返回元素，查不到则返回空指针。
HashNode<K, V>* Find(const K& key) {
Hash hash;
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) return cur;
cur = cur->_next;
}
return nullptr;
}
插入之前，先查找该元素在表中是否存在。若存在则不进行插入，若不存在，先查看负载因子是否等于 1，等于 1 需要扩容。扩容时，由于原来的哈希表中已经有结点了，复用 Insert 的话会创建新结点，造成浪费，所以不进行复用，直接开辟一个新的顺序表，遍历原来的顺序表，将每个哈希桶中的值映射到新表中，将新表和旧表交换即可。扩容结束后，计算出 hashi 来确定新元素要映射的哈希桶，创建新结点，将该结点头插至对应的哈希桶内即可。
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
Hash hash;
// 负载因子为 1 进行扩容
if (_n == _table.size()) {
// 开新表
vector<Node*> newTable;
newTable.resize(__stl_next_prime(_table.size() + 1), nullptr);
// 将原表的数据移动到新表内
for (int i = 0; i < _table.size(); ++i) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hash(cur->_kv.first) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
swap(newTable, _table);
}
size_t hashi = hash(kv.first) % _table.size();
Node* newNode = new Node(kv);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
删除的操作与链表的删除类似，需要一个前驱指针 prev 和当前节点指针 cur。计算出 hashi 来确定元素所在的哈希桶。当 prev 为空指针，cur 指向的为要删除的结点时，那么需要修改头结点的指针，使其指向 cur 的下一个结点，再删除结点 cur。当 prev 为非空指针，cur 指向的为要删除的结点时，就需要修改 prev 结点的 next，使其指向 cur 的下一个结点，再删除结点 cur。如果 cur 遍历至空都没有要删除的值，则不需要删除。
bool Erase(const K& key) {
Hash hash;
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
Node* prev = nullptr;
while (cur) {
if (cur->_kv.first == key && prev == nullptr) {
_table[hashi] = cur->_next;
--_n;
delete cur;
return true;
} else if (cur->_kv.first == key && prev) {
prev->_next = cur->_next;
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
prev 为空时：
prev 不为空时：
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& str) {
size_t ret = 0;
for (auto& ch : str) {
ret += ch;
ret *= 131;
}
return ret;
}
};
// 数据
template<class K, class V>
struct HashNode {
HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
pair<K, V> _kv;
HashNode<K, V>* _next;
};
// 哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
inline unsigned long __stl_next_prime(unsigned long n) {
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
402653189, 805306457, 1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable() {
_table.resize(11, nullptr);
_n = 0;
}
~HashTable() {
for (int i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
// 插入
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) return false;
Hash hash;
// 负载因子为 1 进行扩容
if (_n == _table.size()) {
// 开新表
vector<Node*> newTable;
newTable.resize(__stl_next_prime(_table.size() + 1), nullptr);
// 将原表的数据移动到新表内
for (int i = 0; i < _table.size(); ++i) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hash(cur->_kv.first) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
swap(newTable, _table);
}
size_t hashi = hash(kv.first) % _table.size();
Node* newNode = new Node(kv);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
// 查找
HashNode<K, V>* Find(const K& key) {
Hash hash;
size_t hashi = hash(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) {
Hash hash;
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
Node* prev = nullptr;
while (cur) {
if (cur->_kv.first == key && prev == nullptr) {
_table[hashi] = cur->_next;
--_n;
delete cur;
return true;
} else if (cur->_kv.first == key && prev) {
prev->_next = cur->_next;
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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