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

【C++进阶学习】第九弹——哈希的原理与实现——开放寻址法的讲解

news 来源：原创 2024/9/20 10:55:11

前言：

在前面，我们已经学习了很多存储机构，包括线性存储、树性存储等，并学习了多种拓展结构，效率也越来越高，但是是否有一种存储结构可以在大部分问题中都一次找到目标值呢？哈希可能能实现

一、哈希的概念

二、哈希冲突

三、哈希冲突解决

3.1 开放寻址法

节点结构

插入操作

查找操作

删除操作

打印操作

3.2 链地址法

四、测试代码（开放寻址法）

五、总结

一、哈希的概念

哈希就是一种特殊的存储结构，通过特定的函数，使得数据的存储位置与它的关键码之间建立一种一一映射的关系，这样在查找数据时就可以直接通过关键值来快速查找

通过这种方法：

当我们向其中插入数据时，就可以利用此特定函数插入到关键码对应的位置下

当我们搜索数据时，通过关键码，进行相应的处理就可以找到要找的数据

这种方法就叫做哈希，特定的函数就是哈希函数，这种方法所建立的结构就叫做哈希函表

我们来看这样一个例子：

对于这样一个数组{1，5，3，17，19，0}，按照上述规则我们首先要先找一个合适的哈希函数，

这里我们哈希函数可以设为：hashi(key)=key%capacity；capacity为存储空间底层空间总的大小

现在我们根据上面这个例子来思考这样一个问题，如果有这样一个数据，比如13，通过上面的哈希函数计算得我们应该把它放在关键码为3的位置上，但是此时这个位置上已经有数据了，我们应该如何解决呢？这样的问题就叫做哈希冲突

二、哈希冲突

哈希冲突指的是在使用哈希表进行数据存储和查找时，不同的关键字通过哈希函数计算得到了相同的哈希值。

哈希函数是将关键字映射到哈希表中的某个位置的函数。由于哈希表的存储空间是有限的，而可能的关键字数量是无限的，所以不同的关键字有可能被映射到相同的位置，这就产生了哈希冲突。

哈希冲突会影响哈希表的性能，比如增加查找、插入和删除操作的时间复杂度。

常见的解决哈希冲突的方法有（这两种方法会在后面详细讲解）：

开放寻址法：当发生冲突时，通过一定的探查方式在哈希表中寻找其他空闲的位置来存储冲突的元素。
链地址法：在哈希表的每个位置上建立一个链表，将所有哈希值相同的元素都存储在这个链表中。

三、哈希冲突解决

解决哈希冲突常见的两种方法主要是：开放寻址法和链地址法

3.1 开放寻址法

开放定址法是解决哈希冲突的一种方法，其基本思想是当发生冲突时，通过某种系统的方法在哈希表中寻找下一个空槽位，并将冲突的关键码存储在这个槽位中。下面我们先来看一下开放寻址法的重点：

探测序列：开放定址法中，探测序列决定了当发生冲突时如何查找下一个槽位。常见的探测序列方法有：

线性探测：当冲突发生时，顺序检查表中的下一个槽位，直到找到空槽位。
二次探测：探测序列为 1, 4, 9, 16, ...，即探测位置是 i^2 的倍数，其中 i 是从0开始的整数。
伪随机探测：使用伪随机数生成器来确定探测序列。

删除操作：在开放定址法中，删除元素比较复杂，因为不能简单地将槽位置为空，否则会影响后续的查找操作。通常，删除一个元素时，将其标记为已删除，但在查找时跳过已删除的元素。

装填因子：装填因子是哈希表中已存储元素个数与哈希表大小的比值。开放定址法中，装填因子不宜过高，否则冲突概率增加，查找效率下降。（因为这个原因，所以需要扩容）

节点结构

因为我们并不知道插入要操作何种类型的数据，可能是整形，浮点型或string的，所以我们可以选择将它们全转化为整形来处理，这里就需要我们借助仿函数和模板特化来实现

	template<class K>       
struct HashFunc         //仿函数，这里的功能是将其他类型转化为整形
{size_t operator()(const K& key){return (size_t)key;}
};
template<>     //特化
struct HashFunc<string>    //string类的不可以直接转化为整形，所以需要特殊处理
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};enum Status{EMPTY,     //此位置为空EXIST,     //此位置不为空DELETE     //此位置数据已被删除};template<class K, class V>     //因为不能确定我们要处理什么类型的数据，所以我们采用类模板的形式struct HashData{pair<K, V> _kv;   Status _s;        //此位置的状态};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable()     //初始化HashTable{_tables.resize(10);}private:vector<HashData<K, V>> _tables;size_t _n = 0;        //存储个数};

插入操作

开放寻址法的关键就在于数据的插入，在这里我们重点讲解一下线性探测的思想

这就是线性探测的思路，同时我们还要在装填因子足够大的时候进行扩容，比如上面这个例子，此时10个位置中已经填入7个因子，我们就可以进行按2倍扩容：

代码实现如下：

		//插入bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//负载因子0.7就扩容if (_n * 10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);    //直接交换就可以得到扩容后的结果}Hash hf;//线性探测size_t hashi = hf(kv.first) % _tables.size();  //这里涉及到模板的特化，后面会讲while (_tables[hashi]._s == EXIST)    //当此位置不为空时，就往后找{                                     //当为空或已删除时都是可以放入数据的hashi++;hashi %= _tables.size();        //这里进行这个操作的目的是防止hashi大于_tables.size()}_tables[hashi]._kv = kv;     //找到后将这个位置值改为插入值_tables[hashi]._s = EXIST;   //状态改为存在_n++;return true;}

查找操作

上面的插入操作中，我们首先就先用查找操作看是否已经有这个数据，因为哈希是不允许存在重复数据的，这里我们就来看一下这个查找操作

		//查找HashData<K, V>* Find(const K& key){Hash hf;      //仿函数size_t hashi = hf(key) % _tables.size();   //所有计算都要用仿函数将key转换为整形while (_tables[hashi]._s == EXIST)      //从不为空的位置开始找{if (_tables[hashi]._s != EMPTY&& _tables[hashi]._kv.first == key)return &_tables[hashi];hashi++;hashi %= _tables.size();}return NULL;}

删除操作

我们删除一个数据时，并不能简单的找到这个数据就进行删除，这样会对我们后序很多操作带来不少麻烦，比如我们把4删除了，再找44就会很不容易，这也就是我们前面在定义节点结构是要定义状态的原因，我们删除一个操作后可以把它的状态更改，这样我们在进行其他操作的时候就可以直到这个位置上的值已被删除

		//删除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_s = DELETE;_n--;return 0;}elsereturn true;}

打印操作

		//打印void Print(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST)     //当这个位置有数据时，打印出有效数据cout << "[" << i << "]->" << _tables[i]._kv.first << ":"<< _tables[i]._kv.second << endl;else if (_tables[i]._s == EMPTY)printf("[%d]->EMPTY\n", i);elseprintf("[%d]->DELETE\n", i);}}

3.2 链地址法

链地址法有些东西与上面的代码有些冲突，不好测试，我们放在下一篇讲

四、测试代码（开放寻址法）

我们给出几个测试用例检验一下上面的开放寻址法是否有误：

测试一：

		void TestHT1(){HashTable<int, int> j;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){j.Insert(make_pair(e, e));}j.Insert(make_pair(3, 3));j.Print();j.Insert(make_pair(3, 3));     //这里有一个隐藏的bugif (j.Find(3))cout << "3存在" << endl;}

运行结果：

测试二：

	void TestHT2()    //测试string{string arr[] = { "香蕉","甜瓜","苹果","香蕉","苹果","苹果" };HashTable<string, int> ht;for (auto e : arr){auto ret = ht.Find(e);if (ret)ret->_kv.second++;else{ht.Insert(make_pair(e, 1));}}ht.Print();}

运行结果：