广州分享网站建设,免费分类信息网站源码,广州建设网站的公司哪家好,wordpress打造云笔记文章目录 底层结构哈希冲突闭散列定义哈希节点定义哈希表**哈希表什么情况下进行扩容#xff1f;如何扩容#xff1f;**Insert()函数Find()函数二次探测HashFunc()仿函数Erase()函数全部的代码 开散列定义哈希节点定义哈希表Insert()函数Find()函数Erase()函数总代码 初识哈希… 文章目录 底层结构哈希冲突闭散列定义哈希节点定义哈希表**哈希表什么情况下进行扩容如何扩容**Insert()函数Find()函数二次探测HashFunc()仿函数Erase()函数全部的代码 开散列定义哈希节点定义哈希表Insert()函数Find()函数Erase()函数总代码 初识哈希 哈希表是一种查找效率及其高的算法最理想的情况下查询的时间复杂度为O(1)。 unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率 较低。 底层结构 unordered系列的关联式容器之所以效率更高是因为底层采用了哈希的结构。 哈希是通过对key进行映射然后通过映射值直接去拿到要的数据效率更高平衡树的查找是通过依次比对相对而言就会慢一些。 插入元素通过计算出元素的映射值来后通过映射值把元素插入到储存的位置当中。搜索元素通过计算元素的映射值来取得元素。
哈希方法中使用的转换函数称之为哈希(散列)函数构造出来的结构叫做哈希表(散列表) 例: 集合 {1764591121} 哈希函数为hash(key)key%capacitycapacity为底层空间的最大值。 0123456789111214569 1%101、4%104、7%1010… 但如果我要插入一个11怎么办 这就是一个经典的问题哈希冲突 哈希冲突 解决哈希冲突的两种常见方式就是闭散列和开散列。 闭散列 闭散列也叫开放寻址法当发生冲突的时候我就往后面去找假如1和11去%10都等于1但是1先去把1号坑位占了那么11肯定不能把1的坑位抢了只能往后找有没有没有被占的坑位有的话就放11这个方法叫做线性探测法。 但是我要删除某个值该怎么办呢 0123456789111214569 例如这段数据我把11删掉之后 01234567891214569 2的位置就空出来了当我想要去找21的时候会发现找不到因为找某个值和插入某个值是一样的先确定映射值如果不是当前值就往后面找如果为空就找完了这里2为空不能继续往后找了就要返回查找失败了但是21是存在的呀所以可以对每一个哈希节点进行标记在每一个节点中记录一个状态值是Empty还是Exit还是Delete这样就可以避免上述情况了。 定义哈希节点 //枚举状态enum State{Empty,Exit,Delete};templateclass K,class Vstruct Hash_Node{pairK, V _kv;State _state Empty;};定义哈希表 templateclass K,class Vclass Hash_table{public:typedef Hash_NodeK, V Node;private:vectorNode _tables;size_t _size0;};哈希表什么情况下进行扩容如何扩容 Insert()函数
bool Insert(const pairK,V key){//查重if (Find(key.first)){return false;}//扩容if (_tables.size()0||10*_size / _tables.size()7){//大于7需要扩容size_t newSize _tables.size() 0 ? 10 : 2 * _tables.size();Hash_tableK, VnewHT;newHT._tables.resize(newSize);//新表//复用Insert函数for (auto e : _tables){if (e._state Exit){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}//线性探测size_t hashi key.first % _tables.size();while (_tables[hashi]._state Exit){hashi;hashi % _tables.size();}_tables[hashi]._kv key;_tables[hashi]._state Exit;_size;return true;}Find()函数
Hash_NodeK, V* Find(const K key){if (_tables.size() 0) return nullptr;size_t start key % _tables.size();size_t begin start;while (_tables[start]._state ! Empty){if (_tables[start]._state ! Delete _tables[start]._kv.first key){return _tables[start];}start;start % _tables.size();if (begin start){break;}}return nullptr;}样例测试 void test1(){int arr[] { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };Hash_tableint, inths;for (auto e : arr){hs.Insert(make_pair(e, e));}}测试结果如下 可以看到都是被成功的插入了。 线性探测的优先简单方便。 线性探测的缺点一旦发生哈希冲突了所有的冲突都会堆积在一块会导致查找的效率变得很低。 二次探测 二次探测其实就是每次跳过i的平方个间隔原来的线性探测是一个一个往后找。 0123456789ExitExitExit 比如在1发生了哈希冲突那么线性探测就会去找2位置然后再找3位置直到找到空为止。 但二次探测是1没有i1i的平方等于1找2位置i2i的平方等于4找5位置发现没有元素就直接占位二次探测可以让数据更加分散降低哈希冲突的发生率。 size_t start hash(kv.first) % _tables.size();size_t i 0;size_t hashi start;// 二次探测while (_tables[hashi]._state Exit){i;hashi start i*i;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_size;以上的哈希表只能用来映射int类型的值如果是其他类型就不行了这里可以增加一个仿函数来兼容其他类型这里最重要的是string类型了如何才能将string类型转换为一个数值。
我们可以把ASCII码相加就能得到key了但是面对以下场景就会哈希冲突了。 string str1abc;
string str2acb;
string str3cba;这里有大佬得出过一个结论 hash hash * 131 ch这样可以降低哈希碰撞的概率。 HashFunc()仿函数 templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//特例化模板参数来解决string的问题templatestruct HashFuncstring{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};#pragma once
#includeiostream
#includeset
#includevector
using namespace std;//闭散列
namespace mudan
{templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//特例化模板参数来解决string的问题templatestruct HashFuncstring{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};enum State{Empty,Exit,Delete};templateclass K,class Vstruct Hash_Node{pairK, V _kv;State _state Empty;};templateclass K,class V,class HashHashFuncKclass Hash_table{public:typedef Hash_NodeK, V Node;bool Insert(const pairK,V key){//查重if (Find(key.first)){return false;}//扩容if (_tables.size()0||10*_size / _tables.size()7){//大于7需要扩容size_t newSize _tables.size() 0 ? 10 : 2 * _tables.size();Hash_tableK, VnewHT;newHT._tables.resize(newSize);//新表//复用Insert函数for (auto e : _tables){if (e._state Exit){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hash;//线性探测size_t hashi hash(key.first) % _tables.size();while (_tables[hashi]._state Exit){hashi;hashi % _tables.size();}_tables[hashi]._kv key;_tables[hashi]._state Exit;_size;return true;}Hash_NodeK, V* Find(const K key){if (_tables.size() 0) return nullptr;Hash hash;size_t start hash(key) % _tables.size();size_t begin start;while (_tables[start]._state ! Empty){if (_tables[start]._state ! Delete _tables[start]._kv.first key){return _tables[start];}start;start % _tables.size();if (begin start){break;}}return nullptr;}private:vectorNode _tables;size_t _size;};void TestHT2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString countHT;Hash_tablestring, int countHT;for (auto str : arr){auto ptr countHT.Find(str);if (ptr){ptr-_kv.second;}else{countHT.Insert(make_pair(str, 1));}}}void test1(){int arr[] { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };Hash_tableint, inths;for (auto e : arr){hs.Insert(make_pair(e, e));}}
}可以看到映射也成功了。 对于之前说的问题也解决了。
string str1abc;
string str2acb;
string str3cba; Erase()函数 这个就简单了Erase不是真正意义上把这个数字从数组当中删掉而是改变状态把状态改成Delete即可。 bool Erase(const K key){Hash_NodeK, V* ret Find(key);if (ret){ret-_state Delete;--_size;return true;}else{return false;}}全部的代码
#pragma once
#includeiostream
#includeset
#includevector
using namespace std;//闭散列
namespace mudan
{templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//特例化模板参数来解决string的问题templatestruct HashFuncstring{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};enum State{Empty,Exit,Delete};templateclass K,class Vstruct Hash_Node{pairK, V _kv;State _state Empty;};templateclass K,class V,class HashHashFuncKclass Hash_table{public:typedef Hash_NodeK, V Node;bool Insert(const pairK,V key){//查重if (Find(key.first)){return false;}//扩容if (_tables.size()0||10*_size / _tables.size()7){//大于7需要扩容size_t newSize _tables.size() 0 ? 10 : 2 * _tables.size();Hash_tableK, VnewHT;newHT._tables.resize(newSize);//新表//复用Insert函数for (auto e : _tables){if (e._state Exit){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hash;//线性探测size_t hashi hash(key.first) % _tables.size();while (_tables[hashi]._state Exit){hashi;hashi % _tables.size();}_tables[hashi]._kv key;_tables[hashi]._state Exit;_size;return true;}Hash_NodeK, V* Find(const K key){if (_tables.size() 0) return nullptr;Hash hash;size_t start hash(key) % _tables.size();size_t begin start;while (_tables[start]._state ! Empty){if (_tables[start]._state ! Delete _tables[start]._kv.first key){return _tables[start];}start;start % _tables.size();if (begin start){break;}}return nullptr;}bool Erase(const K key){Hash_NodeK, V* ret Find(key);if (ret){ret-_state Delete;--_size;return true;}else{return false;}}private:vectorNode _tables;size_t _size0;};void TestHT2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString countHT;Hash_tablestring, int countHT;for (auto str : arr){auto ptr countHT.Find(str);if (ptr){ptr-_kv.second;}else{countHT.Insert(make_pair(str, 1));}}}void test1(){int arr[] { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };Hash_tableint, inths;for (auto e : arr){hs.Insert(make_pair(e, e));}}void TestHT3(){HashFuncstring hash;cout hash(abcd) endl;cout hash(bcad) endl;cout hash(eat) endl;cout hash(ate) endl;cout hash(abcd) endl;cout hash(aadd) endl endl;cout hash(abcd) endl;cout hash(bcad) endl;cout hash(eat) endl;cout hash(ate) endl;cout hash(abcd) endl;cout hash(aadd) endl endl;}
}开散列 开散列如上图所示他有一个桶子来表示key值然后key值相同的(哈希冲突的)就都连接到这个桶的key对应的位置下面。 这个桶其实就是一个指针数组。 定义哈希节点 templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK,V* _next;HashNode(const pairK,V data):_kv(data),_next(nullptr){}};定义哈希表
templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:private:vectorNode*_tables;size_t _size0;};Insert()函数 插入操作头插和尾插都很快这里由于定义的是单链表就选择头插了。 插入过程如下图所示 bool Insert(const pairK, V key){Hash hash;//去重if (Find(key.first)) return false;//负载因子等于1就要扩容了if (_size _tables.size()){size_t newsize _tables.size() 0 ? 10:2 * _tables.size();vectorNode*newTables;newTables.resize(newsize);for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hash(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;//销毁原来的桶}_tables.swap(newTables);}//头插// head// 1 2头插2-next1,head2;size_t hashi hash(key.first) % _tables.size();Node* newnode new Node(key);newnode-_next _tables[hashi];_tables[hashi] newnode;_size;return true;}Find()函数 Node* Find(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}//没找到返回空return nullptr;}Erase()函数 和链表的和删除一摸一样 bool Erase(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){// 1、头删// 2、中间删if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}总代码
#pragma once
#includeiostream
#includeset
#includevector
using namespace std;//闭散列
namespace mudan
{templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//特例化模板参数来解决string的问题templatestruct HashFuncstring{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};enum State{Empty,Exit,Delete};templateclass K,class Vstruct Hash_Node{pairK, V _kv;State _state Empty;};templateclass K,class V,class HashHashFuncKclass Hash_table{public:typedef Hash_NodeK, V Node;bool Insert(const pairK,V key){//查重if (Find(key.first)){return false;}//扩容if (_tables.size()0||10*_size / _tables.size()7){//大于7需要扩容size_t newSize _tables.size() 0 ? 10 : 2 * _tables.size();Hash_tableK, VnewHT;newHT._tables.resize(newSize);//新表//复用Insert函数for (auto e : _tables){if (e._state Exit){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hash;//线性探测size_t hashi hash(key.first) % _tables.size();while (_tables[hashi]._state Exit){hashi;hashi % _tables.size();}_tables[hashi]._kv key;_tables[hashi]._state Exit;_size;return true;}Hash_NodeK, V* Find(const K key){if (_tables.size() 0) return nullptr;Hash hash;size_t start hash(key) % _tables.size();size_t begin start;while (_tables[start]._state ! Empty){if (_tables[start]._state ! Delete _tables[start]._kv.first key){return _tables[start];}start;start % _tables.size();if (begin start){break;}}return nullptr;}bool Erase(const K key){Hash_NodeK, V* ret Find(key);if (ret){ret-_state Delete;--_size;return true;}else{return false;}}private:vectorNode _tables;size_t _size0;};void TestHT2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString countHT;Hash_tablestring, int countHT;for (auto str : arr){auto ptr countHT.Find(str);if (ptr){ptr-_kv.second;}else{countHT.Insert(make_pair(str, 1));}}}void test1(){int arr[] { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };Hash_tableint, inths;for (auto e : arr){hs.Insert(make_pair(e, e));}}void TestHT3(){HashFuncstring hash;cout hash(abcd) endl;cout hash(bcad) endl;cout hash(eat) endl;cout hash(ate) endl;cout hash(abcd) endl;cout hash(aadd) endl endl;cout hash(abcd) endl;cout hash(bcad) endl;cout hash(eat) endl;cout hash(ate) endl;cout hash(abcd) endl;cout hash(aadd) endl endl;}
}namespace mudan1
{templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//特例化模板参数来解决string的问题templatestruct HashFuncstring{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK,V* _next;HashNode(const pairK,V data):_kv(data),_next(nullptr){}};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:bool Insert(const pairK, V key){Hash hash;//去重if (Find(key.first)) return false;//负载因子等于1就要扩容了if (_size _tables.size()){size_t newsize _tables.size() 0 ? 10:2 * _tables.size();vectorNode*newTables;newTables.resize(newsize);for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hash(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;//销毁原来的桶}_tables.swap(newTables);}//头插// head// 1 2头插2-next1,head2;size_t hashi hash(key.first) % _tables.size();Node* newnode new Node(key);newnode-_next _tables[hashi];_tables[hashi] newnode;_size;return true;}Node* Find(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}//没找到返回空return nullptr;}bool Erase(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){// 1、头删// 2、中间删if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}private:vectorNode*_tables;size_t _size0;};void TestHT1(){int a[] { 1, 11, 4, 15, 26, 7, 44,55,99,78 };HashTableint, int ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(22, 22));}
}
