C++寻位映射的奇幻密码：哈希
文章目录
- 1.什么是哈希？
- 2.哈希的常见实现方法
- 2.1 直接定址法
- 2.2 除留余数法
- 3.哈希冲突
- 4.哈希冲突的解决
- 4.1 闭散列
- 4.1.1 线性探测
- 4.1.1.1 哈希表的基本数据结构
- 4.1.1.2 哈希表的key转换
- 4.1.1.3 哈希表的插入
- 4.1.1.4 哈希表的查找
- 4.1.1.5 哈希表的删除
- 4.1.2 二次探测
- 4.1.3 线性探测和二次探测对比
- 4.2 开散列
- 4.2.1 哈希桶
- 4.2.1.1 哈希表的基本数据结构
- 4.2.1.2 哈希表的插入
- 4.2.1.3 哈希表的查找
- 4.2.1.4 哈希表的删除
- 4.3 开散列与闭散列比较
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
哈希，用于将任意大小的数据映射为固定长度的数值（哈希值），这个过程通过哈希函数实现，其核心目标是高效地存储、查找和验证数据
1.什么是哈希？
在学哈希之前，我们对于数据的查找通常是建立于顺序表，树形结构的基础上进行的查找，但是随着数据量越来越庞大，数据的随机性和容量越发严峻
理想的搜索方法： 可以不经过任何比较，一次直接从表中得到要搜索的元素
如果构造一种存储结构，通过某种函数( hashFunc )使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素
因此就在此基础上发展出了一种平均时间复杂度几乎为 O(1) 的数据查找方式，哈希，也称为散列
2.哈希的常见实现方法
2.1 直接定址法
对于一段相对集中的数据段，就可以使用直接定址法，这里最大的数是 30，最小的数是15，创建一个大小为 15 的数组，将所有值映射到数组上
优点： 简单、均匀
缺点： 需要事先知道关键字的分布情况
使用场景： 适合查找比较小且连续的情况，数据太分散就不适合了，开的数组会太大，造成空间浪费
2.2 除留余数法
除留余数法是一种通过固定的哈希函数计算方式将数据放入哈希表的常用方法，设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p EXIST, EMPTY, DELETE }; template pair public： HashTable() { _table.resize(10); } private: vector size_t operator()(const K& key) { return (size_t)key; } }; template size_t operator()(const string& str) { // BKDR size_t hash = 0; for (auto ch : str) { hash *= 131; hash += ch; } return hash; } }; // 扩容 //if ((double)_n / (double)_table.size() = 0.7) if (_n * 10 / _table.size() >= 7) { size_t newSize = _table.size() * 2; // 遍历旧表，重新映射到新表 HashTable newHT; newHT._table.resize(newSize); // 遍历旧表的数据插入到新表即可 for (size_t i = 0; i
这里的插入，解决哈希冲突的方式利用的是线性探测的方式：
先对哈希函数计算值所带入的 key 进行处理，转换为合理的计算值，如果计算得出的位置为 EXIST，就依次往后探测，直到找到空位置为止，然后插入即可
那么哈希表满了之后的扩容是怎么一回事呢？
我们要知道判断一个哈希表是否应该开始扩容的标准是负载因子，通过 size / capacity 判断哈希表的填充程度，我们这里设置为 0.7 即扩容
既然扩容了，之前的数据就必须重新计算位置放入哈希表，不然关系就全乱了，或许会有人想为什么不直接新创建一个数组来放？而是创建一个新对象 HashTable newHT，再来创建新哈希表，这是因为在对象里操作可以使用插入等便捷操作，使得新哈希表的创建更方便
🔥值得注意的是：
- 计算位置时除 size，而不是 capacity，因为 size 直接反映了数组的有效长度， capacity 只是为创建更大的数组做准备的，[0, table_size-1] 是索引的合法范围
- hashi %= _table.size() 是为了避免超出数组有效索引范围，只要大于 size 就会被除余回到数组第一个位置
- 有人担心扩容会影响搜索效率，其实影响并不是很大，每次扩容都为之前的两倍，会比之前大很多，也就碰上扩容那一次效率不太高，整体来讲影响是不大的
4.1.1.4 哈希表的查找
HashData* 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*) & _table[hashi]; } ++hashi; hashi %= _table.size(); } return nullptr; }循环条件为 _table[hashi]._state != EMPTY 是因为在插入的时候为空就必定插入，那么查找的过程中在找到新的空之前必定能找到想要的值（如果正确插入的话），if条件还必须加入 _table[hashi]._state == EXIST 是因为避免查找到的是已删除的值
🔥值得注意的是： 返回的是 HashData*，而不是 HashData*，防止 key 被错误修改
4.1.1.5 哈希表的删除
bool Erase(const K& key) { HashData* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } return false; }删除可以说是我们学的那么多个结构里，比插入简单的了，直接删除修改状态即可
4.1.2 二次探测
二次探测的位置计算基于平方序列探测的，下面将给出详细的计算步骤：
- 核心计算公式
给定初始哈希位置 h₀ 和探测次数 i，下一个探测位置为：
h(i) = (h₀ + i²) % table_size
- h₀：初始哈希值（例如 hash(key) % table_size）
- i：探测次数，从 1 开始递增
- table_size：哈希表的大小（必须为素数，否则可能无法覆盖所有槽位）
- 计算步骤示例
假设哈希表大小 table_size = 7（素数），初始哈希位置 h₀ = 3，插入时发生冲突，则二次探测的位置序列为：
探测次数 i 计算公式 结果 h(i) 1 (3 + 1²) % 7 4 2 (3 + 2²) % 7 0 3 (3 + 3²) % 7 5 4 (3 + 4²) % 7 2 5 (3 + 5²) % 7 6 6 (3 + 6²) % 7 1 序列： 3 → 4 → 0 → 5 → 2 → 6 → 1，覆盖所有 7 个槽位
- 为什么表大小必须是素数？
若 table_size 为合数，可能无法覆盖所有槽位。例如，当 table_size = 4（合数）时：
探测次数 i 计算公式 结果 h(i) 1 (h₀ + 1²) % 4 h₀ + 1 2 (h₀ + 2²) % 4 h₀ 3 (h₀ + 3²) % 4 h₀ + 1 序列： h₀ → h₀+1 → h₀ → h₀+1，只能访问 2 个槽位，导致死循环
- 代码实现示例
bool Insert(const pair& kv) { // 扩容逻辑（略） HashFunc hf; size_t h0 = hf(kv.first) % _table.size(); // 二次探测 for (size_t i = 1; i4.1.3 线性探测和二次探测对比
特性 线性探测 二次探测 探测序列 h₀, h₀+1, h₀+2, ... h₀, h₀+1, h₀+4, h₀+9, ... 聚集问题 严重（主聚集） 较轻（二次聚集） 空间利用率 低（易导致连续槽位被占用） 高（更均匀分布） 表满检测 遍历全量槽位即可检测 需遍历约一半槽位 4.2 开散列
4.2.1 哈希桶
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素
闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷，那么有没有办法不把数据只局限在数组里，有的兄弟有的，可以使用拉链法，也叫哈希桶，将数据以单链表的形式挂起来
4.2.1.1 哈希表的基本数据结构
template struct HashNode { pair _kv; HashNode* _next; HashNode(const pair& _kv) :_kv(kv) , _next(nullptr) {} }; template class HashTable { typedef HashNode Node; public: HashTable() { _table.resize(10, nullptr); } ~HashTable() { for (size_t i = 0; i _next; delete cur; cur = next; } _table[i] = nullptr; } } private: vector _table; // 指针数组 size_t _n = 0; // 存储了多少个有效数据 };vector 或者 vector 都是可以的，节点都是指针需要释放，析构函数需要自己实现
4.2.1.2 哈希表的插入
bool Insert(const pair& kv) { if (Find(kv.first)) { return false; } HashFunc hf; // 负载因子到1就扩容 if (_n == _table.size()) { size_t newSize = _table.size() * 2; vector newTable; newTable.resize(newSize, nullptr); // 遍历旧表，顺手牵羊，把节点牵下来挂到新表 for (size_t i = 0; i _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; }由于每个哈希桶可以挂多个数据以节省空间，负载因子可以扩大到 1，平均下来一个桶一个数据
这里悬挂操作是以如图头插的方式进行的，在扩容时，把原先的桶挂到新表上的时候，由于是头插，原先的单链表会在新表上倒置，但是这不影响查找元素，每条桶的元素还是固定的，只是顺序不一样而已
4.2.1.3 哈希表的查找
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; }当查找的节点为头节点时，prev为空，
4.2.1.4 哈希表的删除
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; return true; } prev = cur; cur = cur->_next; } return false; }当查找的节点为头节点时，prev 为空，直接让下一个节点成为头节点即可
当查找的节点为其他节点时，让前一个节点和下一个节点链接
记得释放删除的节点
4.3 开散列与闭散列比较
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销
事实上： 由于开放地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子 a
