做网站用宋体有版权问题吗,机加工外协网站,电子商务网站建设教程试卷,wordpress打赏作者插件#x1f389;博主首页#xff1a; 有趣的中国人 #x1f389;专栏首页#xff1a; C进阶 #x1f389;其它专栏#xff1a; C初阶 | Linux | 初阶数据结构 小伙伴们大家好#xff0c;本片文章将会讲解 哈希函数与哈希 之 闭散列的线性探测解决哈希冲突 的相关内容。 如… 博主首页 有趣的中国人 专栏首页 C进阶 其它专栏 C初阶 | Linux | 初阶数据结构 小伙伴们大家好本片文章将会讲解 哈希函数与哈希 之 闭散列的线性探测解决哈希冲突 的相关内容。 如果看到最后您觉得这篇文章写得不错有所收获麻烦点赞、收藏、留下评论。您的支持是我最大的动力让我们一起努力共同成长 文章目录 1. 哈希概念2. 哈希冲突3. 解决哈希冲突的方法3.1 线性探测的代码实现font color blue size 5b⌛1、枚举类型定义状态⏳font color blue size 5b⌛2、插入元素Insert⏳font color blue size 5b⌛3、查找元素Find⏳font color blue size 5b⌛4、删除元素Erase⏳ 4. 字符串哈希详谈字符串哈希的相关做法 5. 完整代码 1. 哈希概念 ⌛哈希函数的概念⏳
哈希函数是一种将输入数据例如字符串、数字等转换为固定长度的输出数据的函数。这个输出通常称为哈希值或哈希码。 哈希函数的特点是对于相同的输入它总是生成相同的输出而且通常无法根据输出反推出输入。这种特性使得哈希函数在密码学、数据验证和数据检索等领域中非常有用。 ⌛哈希表的概念⏳
哈希表是一种数据结构它利用哈希函数来快速定位存储和检索数据。哈希表由一个数组组成每个数组元素称为桶 b u c k e t bucket bucket或槽 s l o t slot slot。当需要存储数据时哈希函数会将数据的键 k e y key key映射到数组中的一个位置这个位置称为哈希值。数据被存储在这个位置对应的桶中。当需要检索数据时哈希函数会根据键计算出哈希值并在数组中定位到对应的桶然后从这个桶中检索数据。 哈希表的关键之处在于哈希函数的设计要尽可能地使得不同的键映射到不同的桶以减少哈希冲突多个键映射到同一个桶的情况。但即使哈希函数设计得非常好也无法完全避免冲突。因此哈希表通常会使用一些方法来处理冲突例如链表、开放寻址等。 链表法是将哈希表的每个桶设置为一个链表当发生冲突时将新数据添加到对应桶的链表中。开放寻址法则是在发生冲突时顺序地寻找下一个空桶来存储数据。 哈希表的优点是能够以常量时间复杂度进行数据的插入、删除和查找操作使得它在处理大量数据时具有高效性。常见的应用包括哈希集合、哈希映射等。 ⌛哈希函数与哈希表的例子⏳
上图哈希函数是 h a s h ( k e y ) k e y hash(key) key hash(key)key % c a p a c i t y capacity capacity通过哈希函数构造出的表称为哈希表。 2. 哈希冲突 对于两个数据元素的关键字 k i k_i ki和 k j k_j kj( i ! j i ! j i!j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 ⌛哈希冲突的例子⏳ 对于两个不同的输入数据 1 1 1 和 11 11 11通过相同的哈希函数 h a s h ( k e y ) k e y hash(key) key hash(key)key % c a p a c i t y capacity capacity计算出来的结果是相同的这就是哈希冲突。 3. 解决哈希冲突的方法 解决哈希冲突 的两种常见的方法是闭散列 和 开散列 ⌛闭散列的线性探测法⏳
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 k e y key key 存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
线性探测 比如下图中的场景现在需要插入元素 44 44 44先通过哈希函数计算哈希地址 h a s h A d d r hashAddr hashAddr为 4 4 4因此 44 44 44 理论上应该插在该位置但是该位置已经放了值为 4 4 4 的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素 4 4 4如果直接删除掉 44 44 44 查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
3.1 线性探测的代码实现
⌛1、枚举类型定义状态⏳ 在实现删除的思路的时候思路如下
根据哈希函数算出对应的哈希值以此位置为起始点开始向后寻找如果找到与传入 k e y key key 值相等的值则查找成功如果查找到空还未找到则查找失败。
但是这样删除可能会出现以下错误
当出现哈希冲突的时候我们尝试删除对应哈希值位置上的元素没问题但是删除之后再删除另一个元素时哈希值会映射到此位置但是此位置为空会引发错误。插入有哈希冲突的两个值 v 1 和 v 2 v1和v2 v1和v2插入第一个值的时候没问题插入的位置为 l o c 1 loc1 loc1假设此位置后面有一个元素 x x x 在插入第二个元素的时候会沿着顺序查找到为空的位置 l o c 2 loc2 loc2 。插入完成。 如果此时我们要删除 x x x那么此位置就变为空接着删除 v 1 v1 v1没问题删除 v 2 v2 v2 的时候就会出现问题。
因此我们需要有一个标记来记录每个节点的状态
代码
enum Status
{EXIST,DELETE,EMPTY
};templateclass K, class V
struct HashData
{Status _status EMPTY;pairK, V _kv;
};⌛2、插入元素Insert⏳ 插入元素思路
根据哈希函数计算插入的位置如果此位置的状态不为存在直接插入如果此位置的状态为存在向后查找找到第一个状态不等于存在空或者删除的位置进行插入。
Insert代码(version 1)
bool Insert(const pairK, V kv)
{// 哈希函数计算位置size_t hashi kv.first % _table.size();// 状态为存在就加加while (_table[hashi]._status EXIST){hashi;hashi % _table.size();}// 出循环说明找到状态不为存在的位置进行插入_table[hashi]._kv kv;_table[hashi]._status EXIST;_n;return true;
}⌛2.1、负载因子load_factor)⏳
我们可以思考一下什么时候进行扩容呢
首先看一下负载因子的定义
负载因子 l o a d f a c t o r n ÷ t a b l e . s i z e ( ) loadfactor n ÷ table.size() loadfactorn÷table.size()
我们这边控制当负载因子超过 0.7 0.7 0.7 的时候进行扩容扩容思路如下
新定义一个HashTable的对象newht开的空间大小为两倍的原始大小( n e w s i z e 2 ∗ t a b l e . s i z e ( ) newsize 2 * table.size() newsize2∗table.size())遍历原始HashTable对象中的成员变量_table如果状态为存在则调用newht的Insert函数;如果状态不为存在则继续往后加加直到走到原始HashTable中的成员变量_table的_table.size()位置。对两个_table进行交换_table.swap(newht._table)
扩容代码
if (_n * 10 / _table.size() 7)
{// 新空间大小size_t newsize 2 * _table.size();// 定义一个新对象HashTableK, V, Func newHT(newsize);for (size_t i 0; i _table.size(); i){// 如果状态为存在则在新的对象中进行插入if (_table[i]._status EXIST)newHT.Insert(_table[i]._kv);}// 交换两个表_table.swap(newHT._table);
}Insert代码(version 2)
bool Insert(const pairK, V kv)
{if (_n * 10 / _table.size() 7){size_t newsize 2 * _table.size();HashTableK, V, Func newHT(newsize);for (size_t i 0; i _table.size(); i){if (_table[i]._status EXIST)newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);}size_t hashi kv.first % _table.size();while (_table[hashi]._status EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._status EXIST;_n;return true;
}⌛3、查找元素Find⏳ 查找元素的思路
首先根据哈希函数计算出哈希值映射位置以此位置为起始点向后寻找直到找到为空的位置如果在此之间找到与所给的值相等的位置返回此位置的地址 注意这里要判断一下找到的节点的状态是否为删除如果是删除状态那就直接跳过如果不是删除才可以返回此节点的地址。 如果一直到空还未找到说明没有哈希表中没有此元素返回空指针nullptr。
查找代码
HashDataK, V* Find(const K key)
{// 根据哈希函数计算位置size_t hashi key % _table.size();// 如果状态不为空则继续向后查找while (_table[hashi]._status ! EMPTY){// 找到了并且状态不为删除则返回此位置的地址if (_table[hashi]._status ! DELETE _table[hashi]._kv.first key){return _table[hashi];}// 找不到则继续向后找else{hashi;hashi % _table.size();}}// 找到空还未找到返回空指针return nullptr;
}⌛4、删除元素Erase⏳ 删除元素的思路
调用查找函数看是否有此元素如果找到此元素直接对此位置的状态置为DELETE 这就是为什么在查找的时候要判断一下找到的那个节点的位置是否是删除状态如果是删除状态并且返回可能会造成重复删除的可能。 如果未找到则返回false。
删除代码
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret nullptr)return false;else{ret-_status DELETE;return true;}
}4. 字符串哈希 那当我们 插入字符串 的时候应该 用什么样的哈希函数来解决值与位置的对应关系 来实现哈希表呢 当我们插入数字的类型例如double、float、int、 char、unsigned用的是一种类型的哈希函数当我们插入字符串类型string的时候用的是另一种类型的哈希函数遇到这种情况的时候我们一般用仿函数来解决问题
因此我们要加一个仿函数的模板参数class HashFunc
对于数字类型的仿函数代码
templateclass K
struct Hash
{size_t operator()(const K key){// 强转即可return (size_t)key;}
};对于string类型的仿函数代码
这里先写一下待会再细谈
struct StringFunc
{size_t operator()(const string str){size_t ret 0;for (auto e : str){ret * 131;ret e;}return ret;}
};由于string类型的哈希我们经常用因此可以用模板的特化并将此模板用缺省参数的形式传递这样我们就不用在每次用的时候传入仿函数了。
templateclass K
struct Hash
{size_t operator()(const K key){return (size_t)key;}
};template
struct Hashstring
{size_t operator()(const string str){size_t ret 0;for (auto e : str){ret * 131;ret e;}return ret;}
};详谈字符串哈希的相关做法 我们用的哈希函数要尽量减少哈希冲突因此在我们实现字符串转数字的时候也要尽量避免重复数据的出现次数实际上有很多解决方法这里有一篇文章有兴趣的可以看一下 链接 字符串哈希算法 其中讲了好几种哈希算法并进行了很多测试 其中效果最好的就是BKDR字符串哈希算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名是一种简单快捷的hash算法也是Java目前采用的字符串的Hash算法累乘因子为31。
下面代码来自于上述链接
templateclass T
size_t BKDRHash(const T *str)
{ register size_t hash 0; while (size_t ch (size_t)*str) { hash hash * 131 ch; // 也可以乘以31、131、1313、13131、131313.. // 有人说将乘法分解为位运算及加减法可以提高效率如将上式表达为hash hash 7 hash 1 hash ch; // 但其实在Intel平台上CPU内部对二者的处理效率都是差不多的 // 我分别进行了100亿次的上述两种运算发现二者时间差距基本为0如果是Debug版分解成位运算后的耗时还要高1/3 // 在ARM这类RISC系统上没有测试过由于ARM内部使用Booths Algorithm来模拟32位整数乘法运算它的效率与乘数有关 // 当乘数8-31位都为1或0时需要1个时钟周期 // 当乘数16-31位都为1或0时需要2个时钟周期 // 当乘数24-31位都为1或0时需要3个时钟周期 // 否则需要4个时钟周期 // 因此虽然我没有实际测试但是我依然认为二者效率上差别不大 } return hash;
} 5. 完整代码 博主gitee链接 Jason-of-carriben 闭散列哈希 #pragma once
#include iostream
#include vector
using namespace std;namespace open_adress
{enum Status{EXIST,DELETE,EMPTY};templateclass K, class Vstruct HashData{Status _status EMPTY;pairK, V _kv;};struct StringFunc{size_t operator()(const string str){size_t ret 0;for (auto e : str){ret * 131;ret e;}return ret;}};templateclass Kstruct Hash{size_t operator()(const K key){return (size_t)key;}};templatestruct Hashstring{size_t operator()(const string str){size_t ret 0;for (auto e : str){ret * 131;ret e;}return ret;}};templateclass K, class V, class Func HashKclass HashTable{public:HashTable(size_t n 10){_table.resize(n);}bool Insert(const pairK, V kv){HashDataK, V* ret Find(kv.first);if (ret ! nullptr)return false;if (_n * 10 / _table.size() 7){size_t newsize 2 * _table.size();HashTableK, V, Func newHT(newsize);for (size_t i 0; i _table.size(); i){if (_table[i]._status EXIST)newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);for (auto data : _table){if (data._status EXIST)_n;}}Func hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._status EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._status EXIST;_n;return true;}HashDataK, V* Find(const K key){Func hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._status ! EMPTY){if (_table[hashi]._status ! DELETE _table[hashi]._kv.first key){return _table[hashi];}else{hashi;hashi % _table.size();}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret nullptr)return false;else{ret-_status DELETE;return true;}}private:vectorHashDataK, V _table;size_t _n 0;};void HashTest1(){HashTableint, int ht;int arr[] { 10001, 91, 72, 55, 63, 97, 80 };for (auto e : arr){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(93, 93));}void TestHT3(){//HashTablestring, int, StringHashFunc ht;HashTablestring, int ht;ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(left, 1));ht.Insert(make_pair(insert, 1));/*cout StringHashFunc()(bacd) endl;cout StringHashFunc()(abcd) endl;cout StringHashFunc()(aadd) endl;*/}/*void test_map1(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉,苹果,草莓, 苹果,草莓 };unordered_mapstring, int countMap;for (auto e : arr){countMap[e];}cout countMap.load_factor() endl;cout countMap.max_load_factor() endl;cout countMap.size() endl;cout countMap.bucket_count() endl;cout countMap.max_bucket_count() endl;for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl;}*/}
