黄山做网站,企业网站seo推广,深圳勘察设计协会,福州网站建设网站设计网站推广前言
本文将会向你介绍哈希概念#xff0c;哈希方法#xff0c;如何解决哈希冲突#xff0c;以及闭散列与开散列的模拟实现
1. 哈希概念 顺序结构以及平衡树中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在查找一个元素时#xff0c;必须要经…前言
本文将会向你介绍哈希概念哈希方法如何解决哈希冲突以及闭散列与开散列的模拟实现
1. 哈希概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即 O( l o g 2 N log_2N log2N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中 插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功 该方式即为哈希方法哈希方法中使用的转换函数称为哈希函数构造出来的结构称为哈希表(Hash Table)(或者称散列表 例如数据集合{176459} 哈希函数设置为hash(key) key % size; size为存储元素底层空间总的大小。 2. 哈希方法 哈希方法我们通常对关键码key进行转换来确定存储的位置比如由字符串abc转换成一个整数作为存储的位置这个转换的方法称为哈希方法哈希方法中运用的函数叫做哈希函数 (1)直接定址法
ps哈希方法是一个广义的概念而哈希函数是哈希方法的一种具体实现。 1、直接定址法 值和位置关系唯一关系每个值都有一个唯一位置但是值很分散直接定址会导致空间开很大导致空间浪费 此方法运用于关键字范围集中量不大的情况关键字和存储位置是一对一的关系不存在哈希冲突 引入哈希冲突 哈希冲突概念不同关键字通过相同的哈希函数计算出相同的哈希存储位置不同的值映射到相同的位置上去这种现象被称为哈希冲突或哈希碰撞哈希冲突的发生与哈希函数的设计有关 (2)除留余数法
主要应用于关键字可以很分散量可以很大关键字和存储位置是多对一的关系的情况但是存在哈希冲突
3. 解决哈希冲突
(1)闭散列 概念 闭散列又称开放定址法指当前位置被占用哈希冲突开放空间里按照某种规则找一个没有被占用的位置存储 1、线性探测 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止 Hashi hashi i(i0) 2、二次探测 探测公式发生变化 hashi i^2(i0) (2)开散列 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 如图可观察到val值为44的节点和节点val值为4的节点发生哈希冲突 开散列中每个桶中放大都是发生哈希冲突的元素 引入负载因子 负载因子存储个数/空间的大小注意这里的空间的大小是size而不是capacity 由于在哈希表中operator[]操作会根据已有的元素数量即size()进行检查。因此在计算负载因子时要使用已有元素的个数除以哈希表的大小即size() size()函数返回的是当前哈希表中实际存储的元素数量而capacity()函数返回的是哈希表的容量即内部存储空间的大小) 负载因子存储关键字个数/空间大小 负载因子太大冲突可能会剧增冲突增加效率降低 负载因子太小冲突降低但是空间利用率就低了 5. 哈希表扩容 扩容的核心是先开辟新空间然后遍历旧空间的数据按照hashi hashi % Newsize重新建立映射然后将旧空间的数据拷贝到新空间去最后交换新旧哈希表本质上我们还是要对旧哈希表进行扩容因此最后要swap交换两表 6. 哈希表插入
三种状态EMPTY、EXIST、DELETE
EMPTY表示该位置为空。 EXIST表示该位置被占用了。 DELETE表示该位置被删除了。
删除状态存在的含义
或许你会有疑问删除为什么不能直接设为空状态而是将被删除的状态设置为DELETE 7. 闭散列模拟实现
数据结构
struct Elem
{pairK, V _val;State _state EMPTY;
};
vectorElemK, V _ht;闭散列插入
闭散列的插入步骤是判断是否存在判断是否需要扩容结合负载因子遍历旧空间拷贝数据 关于闭散列的模拟实现核心步骤在上文都有讲这里就不再多作赘述具体可看下面的代码与注释
namespace Close_Hash
{templateclass Tstruct HashFunc{size_t operator()(const T key){return (size_t)key;}};//因为字符串做键值非常常见库里面也特化了一份//BKDR算法这里不会展开来讲templatestruct HashFuncstring{size_t operator()(const string key){size_t hashi 0;for (auto ch : key){hashi hashi * 31 ch;}return hashi;}};enum State { EMPTY,EXIST,DELETE};template class K, class Vstruct Elem{pairK, V _val;State _state EMPTY;};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(size_t capacity 3): _ht(capacity),_size(0), _totalSize(0){for (size_t i 0; i capacity; i)_ht[i]._state EMPTY;}// 插入bool Insert(const pairK, V val){Hash hf;_size _ht.size();//已有if (Find(val.first)){return false;}else{//扩容,负载因子0.6if ((double)_totalSize / _size 0.6){//开辟新空间size_t newsize _size * 2;HashTableK, V, Hash NewHt;NewHt._ht.resize(newsize);//遍历旧空间for (int i 0; i _size; i){if (_ht[i]._state EXIST){NewHt.Insert(_ht[i]._val);}}NewHt._ht.swap(_ht);}size_t hashi hf(val.first) % _size;//不为空向后查找while (_ht[hashi]._state EXIST){hashi;//如果超出数组长度hashi % _size;}//为空插入_ht[hashi]._val.first val.first;_ht[hashi]._val.second val.second;_ht[hashi]._state EXIST;_totalSize;return true;}}// 查找ElemK, V* Find(const K key){Hash hf;//线性探测size_t hashi hf(key) % _ht.size();while (_ht[hashi]._state ! EMPTY){ if (_ht[hashi]._state EXIST _ht[hashi]._val.first key){return _ht[hashi];}hashi;//超出数组长度hashi % _ht.size();}//没有找到areturn nullptr;}// 删除bool Erase(const K key){ElemK, V* ret Find(key);//不为空就说明找到if (ret){ret-_state DELETE;--_totalSize;return true;}else return false;}private:size_t HashFunc(const K key){return key % _ht.capacity();}void CheckCapacity();private:vectorElemK, V _ht;size_t _size;size_t _totalSize; // 哈希表中的所有元素有效和已删除, 扩容时候要用到};
}测试 void Print(){for (int i 0; i _ht.size(); i){if (_ht[i]._state EXIST){//printf([%d]-%d\n, i, _tables[i]._kv.first);cout [ i ]- _ht[i]._val.first : _ht[i]._val.second endl;}else if (_ht[i]._state EMPTY){printf([%d]-\n, i);}else{printf([%d]-D\n, i);}}void TestHT1()
{Close_Hash::HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Print();ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();cout endl;ht.Erase(3);;ht.Print();if (ht.Find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(23, 3));ht.Insert(make_pair(3, 3));if (ht.Find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Print();
}
8. 开散列模拟实现
数据结构 struct HashNode{HashNode* _next;pairK, V _val;HashNode(const pairK, V val):_next(nullptr),_val(val){}};typedef HashNodeK, V Node;vectorNode* _ht; 开散列插入
插入的主要逻辑是先查找是否存在判断是否需要扩容依据平衡因子开辟新空间然后遍历旧空间将旧空间的数据拷贝到新空间上需要根据新的映射关系待会会细讲最后插入节点
bool Insert(const pairK, V val)
{Hash hf;//已有if (Find(val.first)){return false;}//扩容,负载因子1if (_totalSize _ht.size()){//开辟新空间size_t newsize _ht.size() * 2;vectorNode* NewHt;NewHt.resize(newsize);//遍历旧空间for (int i 0; i _ht.size(); i){Node* cur _ht[i];while (cur){//保存下一个结构体指针Node* next cur-_next;size_t hashi hf(cur-_val.first) % NewHt.size();//将新空间上hashi位置处的哈希桶链接到需要处理的当前节点cur-_next NewHt[hashi];NewHt[hashi] cur;//处理旧空间上哈希桶的下一个节点cur next;}//防止出现悬空指针的问题_ht[i] nullptr;} _ht.swap(NewHt);}//插入节点size_t hashi hf(val.first) % _ht.size();Node* newnode new Node(val);//头插newnode-_next _ht[hashi];_ht[hashi] newnode;_totalSize;return true;
}以下是遍历旧空间拷贝数据的图解 插入过程图解 全部代码 namespace Open_Hash
{templateclass Tstruct HashFunc{size_t operator()(const T key){if (key 0){return (size_t)key;}else{return abs(key);}}};//字符串哈希算法这里不展开讲采用的是BKDR算法templatestruct HashFuncstring{size_t operator()(const string key){size_t hashi 0;for (auto ch : key){hashi hashi * 31 ch;}return hashi;}};template class K, class Vstruct HashNode{HashNode* _next;pairK, V _val;HashNode(const pairK, V val):_next(nullptr),_val(val){}};templateclass K, class V, class Hash HashFuncKclass HashTable{public: HashTable(){_ht.resize(10);}~HashTable(){for (int i 0; i _ht.size(); i){Node* cur _ht[i];while (cur){Node* next cur-_next;delete cur;cur next;}//将当前哈希桶置空_ht[i] nullptr;}}typedef HashNodeK, V Node;// 插入bool Insert(const pairK, V val){Hash hf;//已有if (Find(val.first)){return false;}//扩容,负载因子1if (_totalSize _ht.size()){//开辟新空间size_t newsize _ht.size() * 2;vectorNode* NewHt;NewHt.resize(newsize);//遍历旧空间for (int i 0; i _ht.size(); i){Node* cur _ht[i];while (cur){//保存下一个结构体指针Node* next cur-_next;size_t hashi hf(cur-_val.first) % NewHt.size();//将新空间上hashi位置处的哈希桶链接到需要处理的当前节点cur-_next NewHt[hashi];NewHt[hashi] cur;//处理旧空间上哈希桶的下一个节点cur next;}//防止出现悬空指针的问题_ht[i] nullptr;}_ht.swap(NewHt);}//插入节点size_t hashi hf(val.first) % _ht.size();Node* newnode new Node(val);//头插newnode-_next _ht[hashi];_ht[hashi] newnode;_totalSize;return true;}//查找Node* Find(const K key){Hash hf;//线性探测size_t hashi hf(key) % _ht.size();Node* cur _ht[hashi];//遍历对应hashi位置处的哈希桶while (cur){if (cur-_val.first key){return cur;}cur cur-_next;}//没有找到return nullptr;}// 删除bool Erase(const K key){Hash hf;Node* ret Find(key);size_t hashi hf(key) % _ht.size();//不为空就说明找到if (ret){Node* cur _ht[hashi];Node* prev nullptr;//遍历当前哈希桶while (cur){if (cur-_val.first key){//判断是头删还是中间位置处的删除if (prev nullptr){_ht[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}prev cur;cur cur-_next;}}//未找到return false;}private:vectorNode* _ht;Node* _next nullptr;size_t _totalSize 0; // 哈希表中的所有元素有效和已删除, 扩容时候要用到};
}测试 //打印void Print1(){for (int i 0; i _ht.size(); i){Node* cur _ht[i];cout [ i ]:;//哈希桶不为空while(cur){cout ( cur-_val.first , cur-_val.second ) -;cur cur-_next;}cout endl;}cout endl;}void Print2(){for (int i 0; i _ht.size(); i){Node* cur _ht[i];//哈希桶不为空while (cur){cout cur-_val.first : cur-_val.second ;cur cur-_next;}}cout endl;}
//测试void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print1();ht.Erase(3);ht.Print1();if (ht.Find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));//ht.Insert(make_pair(-9, -9));ht.Insert(make_pair(-1, -1));ht.Print1();}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashNodestring, int* ret ht.Find(e);if (ret){ret-_val.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print2();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print2();}void Some(){const size_t N 100;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v.push_back(rand()); // N比较大时重复值比较多v.push_back(rand()%100i); // 重复值相对少//v.push_back(i); // 没有重复有序}HashTableint, int ht;for (auto e : v){ht.Insert(make_pair(e, e));}ht.Print1();}小结
今日的分享就到这里啦后续将会向你带来位图与布隆过滤器的知识如果本文存在疏漏或错误的地方还请您能够指出另外如果你存在疑问也可以评论留言哦
