哈希表的介绍和使用
一.哈希表的概念
哈希又称散列，本质是通过一种键值对存储的高校组织方式。通过一个哈希函数，将数据的关键字直接映射到存储的数据中，实现快速的定位。
就像在图书馆中可以根据图书的编号来快速查找图书的位置。
二.直接定址法
直接借用关键字作为存储位置的下标，
class Solution {
public:
int first(string s) {
int count[26] = { 0 };
for (auto e : s) {
count[e - 'a']++;
}
for (size_t i = 0; i < s.size(); i++) {
if (count[s[i] - 'a'] == 1) {
return i;
}
}
return - 1;
}
};
注：查找数组中唯一出现的字符，字符只有26个，直接定义一个数组来记录每个字母出现的次数。
如果数据集中，没有哈希冲突，而且效率高，但是数据如果分散，会造成数据的浪费，甚至内存浪费。
三.哈希冲突
在使用哈希函数进行映射的时候，不可避免地会出现两个不同的关键字映射到同一个下标的情况，这就是哈希冲突。
比如：用 “关键字对 11 取模” 作为哈希函数（M=11），关键字 19 和 30 的计算结果都是 8（19%11=8，30%11=8），这就产生了冲突。
理想情况下，我们希望哈希函数能让关键字均匀分布在数组中，减少冲突，但实际场景中冲突无法完全避免—— 就像图书馆的书架位置有限，总会有新书的编号对应已被占用的位置。因此，哈希表的设计核心包含两部分：
1.设计优秀的哈希函数，减少冲突次数；
2.设计高效的冲突解决机制，处理已发生的冲突。
我们还要介绍一下负载因子：
是衡量哈希表拥挤程度的核心指标，直接影响冲突概率。
负载因子 α = 哈希表中存储的元素个数（N） / 哈希表的数组大小（M）
负载因子与哈希表性能的关系是：
α 越大：哈希表越拥挤，冲突概率越高，查询效率越低；
α 越小：哈希表越宽松，冲突概率越低，但空间利用率越低。
不同冲突解决机制对应的负载因子阈值不同：
开放定址法：α 必须小于 1（因为所有元素都存储在数组中，数组满了就无法插入）；
链地址法：α 可以大于 1（冲突元素会以链表形式挂在数组下标下），STL 的 unordered_map 默认将 α 阈值设为 1，超过则扩容。
四.哈希冲突解决：当关键字 “撞车” 了怎么办？
无论哈希函数设计得多优秀，冲突都无法完全避免。实战中处理哈希冲突的核心方法有两种：开放定址法和链地址法（拉链法）。其中链地址法因实现简单、性能稳定，被广泛应用于 STL 的 unordered_map、Java 的 HashMap 等容器中。
开放定址法：在数组内寻找 “空位”
开放定址法的核心逻辑是：所有元素都存储在哈希表的数组中，当某个关键字的哈希位置被占用时，按照某种规则在数组中寻找下一个空位置存储。
它的约束是：负载因子 α 必须小于 1（数组不能满，否则没有空位可找）。常用的寻找规则有三种：线性探测、二次探测、双重探测。
线性探测：依次向后寻找
线性探测是最简单的开放定址法，规则是：
用哈希函数计算初始位置 hash0 = Key % M；
如果 hash0 被占用，依次探测 hash0+1、hash0+2、…，直到找到空位置；
若探测到数组末尾，回绕到数组开头继续探测（循环探测）。
数学表达式为：h_i (Key) = (hash0 + i) % M（i=1,2,...,M-1）
示例演示
假设 M=11（数组下标 0-10），关键字集合 {19,30,5,36,13,20,21,12}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → 下标 8（被占用，探测 9→空，存储 30）；
5%11=5 → 下标 5（空，存储 5）；
36%11=3 → 下标 3（空，存储 36）；
13%11=2 → 下标 2（空，存储 13）；
20%11=9 → 下标 9（被占用，探测 10→空，存储 20）；
21%11=10 → 下标 10（被占用，探测 0→空，存储 21）；
12%11=1 → 下标 1（空，存储 12）。
最终数组存储结果（下标 0-10）：21、12、13、36、空、5、空、空、19、30、20。
线性探测的问题：群集（堆积）
线性探测的缺点是很明显的：如果某个区域的位置被连续占用，后续冲突的关键字都会往这个区域聚集，形成 “群集”（比如下标 8、9、10 被占用后，后续映射到这些下标的关键字都会探测下标 0）。群集会导致探测次数增多，查询效率下降。
二次探测：平方跳跃式寻找
二次探测的核心是通过平方数跳跃探测，避免线性探测的群集问题。规则是：
初始位置 hash0 = Key % M；
若 hash0 被占用，依次探测 hash0+1²、hash0-1²、hash0+2²、hash0-2²、…；
探测范围限制在 i ≤ M/2（避免重复探测），若探测到负数或超出数组范围，需调整到 [0, M-1] 区间。
数学表达式为：h_i (Key) = (hash0 ± i²) % M（i=1,2,...,M/2）
示例演示
假设 M=11，关键字集合 {19,30,52,63,11,22}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → 探测 8+1²=9（空，存储 30）；
52%11=8 → 探测 8+1²=9（被占用）→ 8-1²=7（空，存储 52）；
63%11=8 → 探测 8+1²=9（被占用）→ 8-1²=7（被占用）→ 8+2²=12→1（空，存储 63）；
11%11=0 → 下标 0（空，存储 11）；
22%11=0 → 探测 0+1²=1（被占用）→ 0-1²=-1→10（空，存储 22）。
二次探测能有效减少群集，但无法完全避免 —— 如果关键字的哈希值分布不均匀，仍可能出现局部群集。
双重探测：用第二个哈希函数计算偏移量
双重探测（也叫双散列）的核心是用第二个哈希函数计算探测的偏移量，让探测路径更分散。规则是：
第一个哈希函数计算初始位置 hash0 = h1 (Key) = Key % M；
第二个哈希函数计算偏移量 step = h2 (Key)（要求 step < M 且与 M 互质）；
若 hash0 被占用，依次探测 hash0+step、hash0+2×step、…，直到找到空位置。
数学表达式为：h_i (Key) = (hash0 + i×h2 (Key)) % M（i=1,2,...,M-1）
关键要求：h2 (Key) 与 M 互质
h2 (Key) 必须与 M 互质（最大公约数为 1），否则探测路径会局限在部分位置，无法遍历整个数组。常用的 h2 (Key) 设计：
当 M 为 2 的整数次幂时，h2 (Key) 取奇数（奇数与 2 的整数次幂互质）；
当 M 为质数时，h2 (Key) = Key % (M-1) + 1（确保 step 在 [1, M-1] 之间，且与 M 互质）。
示例演示
假设 M=11（质数），h2 (Key)=Key%10+1，关键字集合 {19,30,52,74}：
19%11=8 → 下标 8（空，存储 19）；
30%11=8 → step=30%10+1=1 → 探测 8+1=9（空，存储 30）；
52%11=8 → step=52%10+1=3 → 探测 8+3=11→0（空，存储 52）；
74%11=8 → step=74%10+1=5 → 探测 8+5=13→2（空，存储 74）。
双重探测的探测路径最分散，能最大程度避免群集，是开放定址法中性能最优的方案，但实现相对复杂。
开放定址法的删除问题：状态标识
开放定址法的一个关键问题是删除元素不能直接置空—— 如果直接将某个位置置空，后续探测该位置的关键字会误以为 “前面没有冲突元素”，导致查找失败。
比如前面的线性探测示例中，若删除下标 9 的 30，直接将下标 9 置空，后续查找 20 时，探测到下标 9 为空就会停止，无法找到下标 10 的 20。
解决该问题的方案是给每个位置增加状态标识：
EMPTY：初始状态，该位置从未存储过元素；
EXIST：该位置当前存储着元素；
DELETE：该位置的元素已被删除，可重新存储。
查找时，只有遇到 EMPTY 状态才停止探测；删除时，将状态改为 DELETE 而非置空；插入时，可将元素存储到 DELETE 或 EMPTY 状态的位置。
链地址法（拉链法）：冲突元素 “链表化”
链地址法是实战中最常用的冲突解决机制，STL 的 unordered_map、Java 的 HashMap 都采用这种方式。它的核心逻辑是：
哈希表的底层是一个指针数组（桶数组），每个元素是一个链表的头指针；
用哈希函数计算关键字的桶下标（hash = Key % M）；
若该桶为空，直接将元素作为链表头节点插入；
若该桶已有关键字（冲突），将元素插入到链表的头部或尾部。
简单说，链地址法是将冲突的关键字 “串成链表”，挂在对应的桶下面，因此也叫 “哈希桶”。
示例演示
假设 M=11，关键字集合 {19,30,5,36,13,20,21,12,24,96}：
19%11=8 → 桶 8 链表：19；
30%11=8 → 桶 8 链表：30 → 19；
5%11=5 → 桶 5 链表：5；
36%11=3 → 桶 3 链表：36；
13%11=2 → 桶 2 链表：13；
20%11=9 → 桶 9 链表：20；
21%11=10 → 桶 10 链表：21；
12%11=1 → 桶 1 链表：12；
24%11=2 → 桶 2 链表：24 → 13；
96%11=8 → 桶 8 链表：96 → 30 → 19。
最终桶数组结构如下（下标 0-10）：
链地址法的优势
相比开放定址法，链地址法有明显优势：
无群集问题：冲突元素只在各自的链表中存储，不影响其他桶；
负载因子可大于 1：链表可以无限延长（理论上），无需严格限制负载因子；
删除简单：直接删除链表节点即可，无需状态标识；
空间利用率高：桶数组可以按需扩容，链表节点只在有冲突时创建。
极端场景优化：链表转红黑树
链地址法的唯一缺点是：如果某个桶的链表过长（比如恶意攻击或关键字分布极端），查询效率会降至 O (n)。为了解决这个问题，Java 8 的 HashMap 引入了优化：当链表长度超过阈值（默认 8）时，将链表转换为红黑树，查询效率提升至 O (log n)。
STL 的 unordered_map 没有这个优化，因为它假设哈希函数足够优秀，链表过长的场景极少发生。实际开发中，只要哈希函数设计合理，无需额外处理。
五.实现链地址法
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 哈希仿函数：支持整数Key
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
// 字符串Key的特化仿函数（BKDR哈希）
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) {
hash = hash * 131 + ch;
}
return hash;
}
};
namespace hash_bucket {
// 哈希链表节点
template<class K, class V>
struct HashNode {
pair<K, V> _kv; // 键值对
HashNode<K, V>* _next; // 下一个节点指针
// 构造函数
HashNode(const pair<K, V>& kv)
: _kv(kv)
, _next(nullptr) {}
};
// 链地址法哈希表（哈希桶）
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
typedef HashNode<K, V> Node;
vector<Node*> _tables; // 桶数组（存储链表头指针）
size_t _n = 0; // 存储的元素个数
// 质数表：用于扩容
static const unsigned long __stl_prime_list[];
static const int __stl_num_primes;
// 获取下一个质数
unsigned long __stl_next_prime(unsigned long n) {
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:
// 构造函数：初始化桶数组为第一个质数（53），所有桶为空指针
HashTable() {
_tables.resize(__stl_next_prime(0), nullptr);
}
// 析构函数：释放所有节点和桶数组
~HashTable() {
// 遍历每个桶，释放链表节点
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr; // 桶置空
}
}
// 插入键值对：头插法，效率O(1)
bool Insert(const pair<K, V>& kv) {
// 查找是否已存在，避免重复插入
if (Find(kv.first) != nullptr) {
return false;
}
// 负载因子≥1，扩容
if (_n == _tables.size()) {
// 新桶数组大小为下一个质数
size_t newSize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newTables(newSize, nullptr);
Hash hash;
// 遍历旧桶，将节点重新映射到新桶
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next; // 保存下一个节点
// 计算节点在新桶中的位置
size_t hashi = hash(cur->_kv.first) % newTables.size();
// 头插法插入新桶
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next; // 处理下一个节点
}
_tables[i] = nullptr; // 旧桶置空
}
// 交换新旧桶数组
_tables.swap(newTables);
}
Hash hash;
size_t hashi = hash(kv.first) % _tables.size(); // 计算桶下标
// 头插法插入新节点
Node* newNode = new Node(kv);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
// 查找Key：返回节点指针，不存在返回nullptr
Node* Find(const K& key) {
Hash hash;
size_t hashi = hash(key) % _tables.size(); // 找到对应的桶
Node* cur = _tables[hashi];
// 遍历链表查找
while (cur) {
if (cur->_kv.first == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}
// 删除Key：成功返回true，不存在返回false
bool Erase(const K& key) {
Hash hash;
size_t hashi = hash(key) % _tables.size(); // 找到对应的桶
Node* prev = nullptr;
Node* cur = _tables[hashi];
// 遍历链表查找要删除的节点
while (cur) {
if (cur->_kv.first == key) {
// 找到节点，删除
if (prev == nullptr) {
// 要删除的是头节点，更新桶的头指针
_tables[hashi] = cur->_next;
} else {
// 要删除的是中间节点， prev->next指向cur->next
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
// 移动指针
prev = cur;
cur = cur->_next;
}
return false;
}
// 获取元素个数
size_t Size() const {
return _n;
}
// 判空
bool Empty() const {
return _n == 0;
}
// 打印哈希表（调试用）
void Print() {
for (size_t i = 0; i < _tables.size(); ++i) {
cout << "桶" << i << ": ";
Node* cur = _tables[i];
while (cur) {
cout << cur->_kv.first << "→" << cur->_kv.second << " ";
cur = cur->_next;
}
cout << endl;
}
cout << "当前元素个数：" << _n << endl;
cout << "当前负载因子：" << (double)_n / _tables.size() << endl;
}
// 禁止拷贝构造和赋值（简化实现，如需支持可自行添加深拷贝）
HashTable(const HashTable&) = delete;
HashTable& operator=(const HashTable&) = delete;
};
// 初始化质数表
template<class K, class V, class Hash>
const unsigned long HashTable<K, V, Hash>::__stl_prime_list[] = {
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
};
template<class K, class V, class Hash>
const int HashTable<K, V, Hash>::__stl_num_primes = sizeof(__stl_prime_list) / sizeof(__stl_prime_list[0]);
}
// 测试代码
int main() {
hash_bucket::HashTable<string, int> ht;
// 插入测试
ht.Insert({"apple", 10});
ht.Insert({"banana", 20});
ht.Insert({"orange", 30});
ht.Insert({"grape", 40});
ht.Insert({"pear", 50});
ht.Insert({"watermelon", 60});
ht.Insert({"pineapple", 70});
cout << "插入后哈希表：" << endl;
ht.Print();
cout << endl;
// 查找测试
auto orange = ht.Find("orange");
if (orange) {
cout << "查找orange：" << orange->_kv.first << " → " << orange->_kv.second << endl;
} else {
cout << "查找orange：未找到" << endl;
}
auto peach = ht.Find("peach");
if (peach) {
cout << "查找peach：" << peach->_kv.first << " → " << peach->_kv.second << endl;
} else {
cout << "查找peach：未找到" << endl;
}
cout << endl;
// 删除测试
bool ret = ht.Erase("grape");
cout << "删除grape：" << (ret ? "成功" : "失败") << endl;
cout << "删除后哈希表：" << endl;
ht.Print();
cout << endl;
// 插入重复Key
ret = ht.Insert({"apple", 15});
cout << "插入重复的apple：" << (ret ? "成功" : "失败") << endl;
cout << "最终哈希表：" << endl;
ht.Print();
return 0;
}
注：哈希表的冲突和扩容需要结合具体的情况来解决！！！
