当前位置：首页 > news >正文

C++数据结构哈希表的实现（开散列实现、闭散列实现）

news 来源：原创 2025/8/13 0:53:59

C++哈希

1. 哈希概念

哈希作为数据结构时，是一种通过某种哈希函数使元素的存储位置与它的关键码之间建立一一映射的关系，在查找时通过该函数就能快速找到该元素，平均时间复杂度为 $\rm O(1)$ ，且遍历结果是无序的。

2. 哈希函数

2.1 直接定址法（常用）

直接定址法，使用关键字本身或关键字的某个线性函数作为哈希地址，哈希函数：
$h(k)=a\times k+b\quad (其中a、b是常数)$
优点： 简单高效，计算速度快。

缺点： 需要提前知道关键字的分布情况。

使用场景： 适用于查找数据量比较小且连续的情况。

2.2 留除余数法（常用）

留除余数法，用关键字除以一个正整数 m，然后取其余数作为哈希地址，哈希函数：
$k\! \mod m\quad (m \;通常取质数)$
优点： $m$ 通常取质数，可以减少哈希冲突的概率。

缺点： 对于特定分布的关键字，可能会出现聚集现象，冲突较多。

使用场景： 适用于关键字分布随机的情况。

2.3 平方取中法

平方取中法，将关键字平方后，取中间几位作为哈希地址，哈希函数：
$h(k)=k^2$
优点： 对关键字的局部性敏感，分布较均匀进一步减少哈希冲突概率）。

缺点： 哈希函数构造稍复杂。

使用场景： 利用平方扩展了关键字的分布范围，适合关键字位数少的情况。

2.4 其他方法

折叠法，将关键字分成若干部分（可以是等长或不等长），然后将这些部分叠加或按某种规则组合，最后取模。
随机数法，利用随机数生成器对关键字产生随机映射。
数学分析法，通过分析关键字的分布特点，设计一个适合的哈希函数，使关键字尽可能均匀分布在哈希表中。

3. 哈希冲突

哈希冲突（Hash Collision）是指在使用哈希函数时，两个或多个不同的关键字被映射到同一个哈希地址的情况。由于哈希表的存储空间有限，而关键字集合可能非常大，完全避免冲突通常是不现实的。因此，如何有效处理哈希冲突是哈希表设计的重要部分。

3.1 闭散列/开放地址法

3.1.1 闭散列的原理

开放地址法，是在发生冲突时，按某种探查规则在哈希表中寻找下一个空闲位置存储数据。

开放地址法的常用方法是线性探测，在发生哈希冲突时，地址依次递增 $i$ ，直到找到下一个空闲的地址为止：

Hash1

图片中 $i$ 为 1。

除了线性探测之外，还有：

二次探测： 步长取 $1)^{-k} i^2\, (k为探测次数)$ 。
双重散列： 使用另一个哈希函数计算步长。

开放地址法的一个问题是，在代码层面上，不能够删除哈希表中已有的元素，因为直接删除元素会影响其他元素的搜索。在代码中，查找元素的逻辑是：

Hash2

问题就出在判断哈希地址是否为空的步骤，如果采用直接删除，在之前的插入图片中，删除掉 4，查找 44，在 $ha s h (44)$ 时，首先访问的是 4 原本的地址，判断地址元素为空，直接判断元素不存在，而如果不使用这种查找方法，就会丢失哈希表查找时间复杂度 $O (1)$ 的特点。

所以在开放地址法中，不能直接删除元素，而是使用一个标记位将其视为无效。

enum State{EMPTY, EXIST, DELETE}

3.1.2 装填因子

装填因子是哈希表满程度的标志因子。状态因子的定义为： $\alpha=表中有效元素个数/哈希表的总长度$

在不清楚实际插入数据的规模的情况下，难免需要对哈希表进行扩容。但在哈希表接近满的情况下，新插入的元素往往会发生很多次哈希冲突才能插入，因此实际设计中不能真的等待哈希表满时扩容，而是在哈希表的哈希冲突概率比较高时，就进行扩容，装填因子就是用来判断是否需要扩容的依据。

对于开放定址法，装填因子应该严格控制在 $0.7 - 0.8$ 以下，如 Java 的系统库限制了装填因子上限为 $0.75$ ，超过该值就对哈希表进行扩容。因此，开放定址法的最大缺陷，就是空间利用率比较低。

开放定址法的扩容的损耗也是一个痛点，因为每次扩容，哈希映射也要跟着改变，已插入的元素都要重新插入哈希表中。哈希扩容需要重新映射，当次插入效率会比较低。重新映射后原来冲突的数据会分开，整体数据更分散。

3.1.3 闭散列的实现

代码主要实现线性探测和哈希函数的处理。

代码：

#include "Hash.hpp"
#include <vector>
#include <iostream>
using namespace std;enum class State
{EMPTY,EXIST,DELETE
};template <class K, class V>
class Element
{
public:pair<K, V> _data;State _state = State::EMPTY;
};template <class K>
class HashFunc
{
public:size_t operator()(const K& Key){return (size_t)Key;}
};template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable() : _table(10), _size(0) {};bool Insert(const pair<K, V>& kv){if (Find(kv.first)){// 如果数据已经存在，就不需要插入return false;}if (_size * 10 / _table.size() >= 7) // 当负载因子大于70%时扩容{// 创建一个新表，将原数据复制到新表中HashTable<K, V> newTB;newTB._table.resize(_table.size() * 2);for (size_t i = 0; i < _table.size(); i++){newTB.Insert(_table[i]._data);}// 交换新表和旧表的地址，并销毁旧表_table.swap(newTB._table);}// 线性探测Hash hash;size_t ptr = hash(kv.first) % _table.capacity();while (_table[ptr]._state == State::EXIST){++ptr;ptr %= _table.capacity();}_table[ptr]._data = kv;_table[ptr]._state = State::EXIST;return true;}Element<K, V>* Find(const K& key){Hash hash;size_t ptr = hash(key) % _table.capacity();// 线性探测while (_table[ptr]._state != State::EMPTY){if (_table[ptr]._state == State::EXIST && _table[ptr]._data.first == key){return &_table[ptr];}++ptr;ptr %= _table.size();}return nullptr;}bool Erase(const K& key){Element<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = State::DELETE;--_size;}return true;}void print(){for (int i = 0; i < _table.size(); i++){if (_table[i]._state == State::EMPTY){cout << "pos:" << i << " " << "state:EMPTY" << " " << "key:" << _table[i]._data.first << " " << "val:" << _table[i]._data.second << endl;}else if (_table[i]._state == State::EXIST){cout << "pos:" << i << " " << "state:EXIST" << " " << "key:" << _table[i]._data.first << " " << "val:" << _table[i]._data.second << endl;}else{cout << "pos:" << i << " " << "state:DELETE" << " " << "key:" << _table[i]._data.first << " " << "val:" << _table[i]._data.second << endl;}}}private:vector<Element<K, V>> _table;size_t _size;
};int main()
{HashTable<int, int> ht;ht.Insert(make_pair(1, 1));ht.Insert(make_pair(3, 75));ht.Insert(make_pair(4, 35));ht.Insert(make_pair(22, 9));ht.Insert(make_pair(33, 1));ht.print();return 0;
}

效果：

Hash3

如果数据类型是 String 或其他类型，可以使用模板的特化指定哈希值的计算方法：

template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};

3.2 开散列/哈希桶/拉链法

3.2.1 开散列的原理

开散列法又叫链地址法，它首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一集合，每一个子集称为一个桶，各个桶中的元素通过一个单链表连接起来，各链表的头节点存储在哈希表中。简单来说，开散列就是闭散列中，发生哈希冲突不另寻地址，而是直接冲突的位置接上数值。

Hash4

3.2.2 开散列扩容

随着插入的元素增多，每个桶中的元素个数也会不断增多，极端情况下，可能会导致一个桶中链表节点非常多，从而影响哈希表的性能。因此需要对哈希表进行扩容。最理想的扩容情况是，每个哈希桶中只有一个节点，此时再进行插入元素时，每次都会发生哈希冲突。因此，在哈希表中元素个数刚好等于桶的个数（即哈希表的容量）时，对哈希表进行扩容。

3.2.3 开散列的实现

插入时，为了代码简洁使用的是头插。