建站平台入口,7游网页游戏平台,网站建站 上海,wordpress 常规选项#x1f680;个人主页#xff1a;小羊 #x1f680;所属专栏#xff1a;C 很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~ 目录 一、哈希结构1、哈希概念2、哈希函数3、哈希冲突3.1 闭散列3.2 开散列 4、完整代码 一、哈希结构
1、哈希概念
A… 个人主页小羊 所属专栏C 很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~ 目录 一、哈希结构1、哈希概念2、哈希函数3、哈希冲突3.1 闭散列3.2 开散列 4、完整代码 一、哈希结构
1、哈希概念
AVL树、红黑树等平衡树搜索效率取决于搜索过程中的比较次数一般时间复杂度为O(logN)虽然平衡树的搜索效率已经很快但如果可以不经过任何比较或者常数次的比较后就能搜索到我们要找的元素会极大的提高效率。 哈希结构是一种通过特定函数哈希函数将关键码映射到表中的一个位置那么在查找时通过该函数就可以很快的找到该元素。 但是上述的映射方法存在一个问题就是不同的元素可能会映射到同一个位置这时就发生了哈希冲突也叫哈希碰撞解决哈希冲突是实现哈希结构的关键。 2、哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不合理。 哈希函数的设计要保证高效性和可靠性
一致性确保相同的输入总是产生相同的输出哈希值均匀分布哈希值应在哈希表的地址空间中尽可能均匀分布以减少哈希冲突计算效率哈希函数应简单且计算快速以便在实际应用中能够快速执行冲突最小化设计哈希函数时应尽量减少哈希冲突的发生以提高哈希表的性能
| 常见哈希函数 哈希函数是哈希表的核心它决定了如何将关键字映射到哈希地址。
直接定制法取关键字的某个线性函数为散列地址Hash(Key)A*KeyB。这种方法简单、均匀但需要事先知道关键字的分布情况除留余数法取一个不大于哈希表地址数m的质数p按照哈希函数Hash(key)key%p将关键码转换成哈希地址。这种方法实现简单且当p选择合理时哈希冲突的概率较低平方取中法对关键字进行平方运算然后抽取中间的几位作为哈希地址。这种方法适用于不知道关键字分布情况且位数不是很大的场景折叠法将关键字从左到右分割成位数相等的几部分最后一部分位数可以短些然后将这几部分叠加求和并按哈希表表长取后几位作为哈希地址。这种方法适用于关键字位数较多的情况
此外还有随机数法、数学分析法等哈希函数设计方法可以根据具体应用场景选择合适的哈希函数。 哈希函数设计的越好产生哈希冲突的可能性就越低但是哈希冲突还是无可避免。 3、哈希冲突 解决哈希冲突的两种常见方法是闭散列开放定址法和开散列链地址法。 3.1 闭散列
当发生哈希冲突时如果哈希表中还有空位置就把key存放到冲突位置的“下一个”空位置去。找下一个空位置常见的探测方法有线性探测、二次探测和双重散列等。
| 线性探测 从发生冲突的位置开始依次向后探测直到找到下一个空位置为止。 插入 上图中在插入15前通过哈希函数得到映射位置为5但是5位置被占了就依次向后找在7位置找到了一个空位置将15插入。删除 闭散列解决哈希冲突时不好随便物理删除某个元素可以考虑标记的方法来伪删除一个元素。
//每个位置都给标记
enum State
{EXIST,//存在DELETE,//删除EMPTY//空
}| 线性探测实现
enum State
{EXIST,EMPTY,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};templateclass K, class V
class HashTable
{
public:HashTable(){_tables.resize(10);//提前开10个位置} private:vectorHashDataK, V _tables;size_t _n 0;//存储元素个数
};插入
关键码对表的size()取模不能对capacity()取模因为哈希表支持[]访问只能访问下标小于size()的元素。 散列表的载荷因子 表中的元素个数 / 表的大小 当载荷因子达到某个临界值就需要扩容。载荷因子越大产生冲突的可能性就越大相反产生冲突的可能性就越小。通常载荷因子应限制在0.7-0.8一下。
不能直接对原表进行扩容无论是原地扩还是异地扩都会把原数据拷贝过来。但是扩完容后元素的相对位置可能会发生改变原本冲突的元素扩完容后就不冲突了所以直接对原表进行扩容是不行的。 扩容有两种方法
方法一新建原表两倍大小的vector遍历原表的元素重新映射到vector中再将新建的vector和原表的vector交换。方法二因为方法一还需要重写一遍映射过程所以可以直接新建一个哈希表遍历原表的元素插入到新建的哈希表中最后交换两个哈希表的vector这个方法的好处是新建的哈希表复用了原哈希表的Insert。
方法一我们就不实现了直接用更好一点的方法二
bool Insert(const pairK, V kv)
{if (_n * 10 / _tables.size() 7)//载荷因子达到一定的值进行扩容{HashTableK, V newHT;newHT._tables.resize(2 * _tables.size());for (int i 0; i _tables.size(); i){if (_tables[i]._state EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t hashi kv.first % _tables.size();//确定映射位置while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();//防止越界}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}但是现在还有个问题在上面的代码中要求我们的key可以取模也就是key只能是无符号整数如果是浮点数、字符串等上面的代码就行不通所以还需要想办法将可能出现的浮点数、字符串等类型的key转换为无符号的整型再做映射。
像浮点数等可以直接强转为无符号整型可以考虑用仿函数解决。字符串一般不能直接强转为无符号整型我们可以对字符串特殊处理也就是模版特化将字符串中字符的ASCII码值加起来作为映射值。 但是这里还有个问题将字符串中字符的ASCII码值加起来也可能冲突比如相同的字符按不同的顺序组合起来的字符串。不过好在有专门的字符串哈希函数字符串哈希函数有好多种这里使用其中一种BKDR Hash函数这里就不做过多介绍了有兴趣的同学请百度了解。他给出的解决办法是字符每次相加之前3131、131、1313、13131…都行来尽可能减少冲突。
templateclass K
struct HashFunc //key强转为整型
{size_t operator()(const K key){return (size_t)key;}
};//对string类型特殊处理
template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash hash * 31 e;}return hash;}
};删除
删除指定的元素只需要找到该元素的位置将该位置的状态标记为DELETE即可。
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret nullptr){return false;}else{ret-_state DELETE;return true;}
}查找
查找过程需要注意的是当在表中找到被查找的元素时还要判断此位置是否被标记为已删除因为删除操作我们并没有实际物理上的删除某个元素。
HashDataK, V* Find(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;
}线性探测的优点是简单好理解缺点是数据容易堆积查找时可能需要多次比较。 闭散列 / 开放定址法我们就先实现到这里它是一种零和博弈和下面将要介绍的开散列 / 链地址法对比还是稍逊一筹。 3.2 开散列
通过哈希函数计算散列地址具有相同映射地址的元素归于同一子集合每一个子集合称为一个哈希桶各个桶中的元素通过一个单链表链接起来哈希表中存各链表的头节点。开散列每个桶中存放的都是产生哈希冲突的元素。 templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash hash * 31 e;}return hash;}
};templateclass K, class V
struct HashNode
{HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}pairK, V _kv;HashNodeK, V* _next;
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(){_tables.resize(10, nullptr);}~HashTable(){for (int i 0; i _tables.size(); i){Node* pcur _tables[i];while (pcur){Node* next pcur-_next;delete pcur;pcur next;}_tables[i] nullptr;}}private:vectorNode* _tables;size_t _n 0;
};插入
bool Insert(const pairK, V kv)
{size_t hashi kv.first % _tables.size();//负载因子1就扩容if (_n _tables.size()){HashTableK, V newHT;newHT._tables.resize(2 * _tables.size(), nullptr);for (int i 0; i _tables.size(); i){Node* pcur _tables[i];while (pcur){newHT.Insert(pcur-_kv);pcur pcur-_next;}}_tables.swap(newHT._tables);}Node* newnode new Node(kv);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}上面的扩容过程虽然可行但是不够好。假如原表中有很多个节点新建新表扩容后复用Insert就要new很多个节点再插入这实际上是很有消耗的。因为原节点和新new的节点并无差别所以可以直接将原表中的节点拿下来头插到新表中这样就不用再new新节点。
| 优化
bool Insert(const pairK, V kv)
{size_t hashi hs(kv.first) % _tables.size();//负载因子1就扩容if (_n _tables.size()){vectorNode* newtables(2 * _tables.size(), nullptr);for (int i 0; i _tables.size(); i){Node* pcur _tables[i];while (pcur){Node* next pcur-_next;size_t hashi pcur-_kv.first % newtables.size();pcur-_next newtables[hashi];newtables[hashi] pcur;pcur next;}_tables[i] nullptr;}_tables.swap(newtables);}Node* newnode new Node(kv);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}删除
学习过链表我们知道单链表的头删和其他位置的删除需要分开处理因为其他位置删除节点后要将前后节点链接起来而单链表的头节点没有前一个节点。
bool Erase(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();Node* pcur _tables[hashi];Node* prev nullptr;while (pcur){if (pcur-_kv.first key){if (prev nullptr){_tables[hashi] pcur-_next;}else{prev-_next pcur-_next;}delete pcur;--_n;return true;}prev pcur;pcur pcur-_next;}return false;
}4、完整代码
namespace open_address
{enum State{EXIST,EMPTY,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass Kstruct HashFunc //key强转为整型{size_t operator()(const K key){return (size_t)key;}};//对string类型特殊处理templatestruct HashFuncstring{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash hash * 31 e;}return hash;}};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);//提前开10个位置}bool Insert(const pairK, V kv){//去冗余if (Find(kv.first)){return false;}if (_n * 10 / _tables.size() 7)//载荷因子达到一定的值进行扩容{HashTableK, V, Hash newHT;newHT._tables.resize(2 * _tables.size());for (int i 0; i _tables.size(); i){if (_tables[i]._state EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi hs(kv.first) % _tables.size();//确定映射位置while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();//防止越界}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret nullptr){return false;}else{ret-_state DELETE;return true;}}private:vectorHashDataK, V _tables;size_t _n 0;//存储元素个数};
}namespace close_address
{templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct HashFuncstring{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash hash * 31 e;}return hash;}};templateclass K, class Vstruct HashNode{HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}pairK, V _kv;HashNodeK, V* _next;};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_tables.resize(10, nullptr);}~HashTable(){for (int i 0; i _tables.size(); i){Node* pcur _tables[i];while (pcur){Node* next pcur-_next;delete pcur;pcur next;}_tables[i] nullptr;}}bool Insert(const pairK, V kv){Hash hs;size_t hashi hs(kv.first) % _tables.size();负载因子1就扩容//if (_n _tables.size())//{// HashTableK, V newHT;// newHT._tables.resize(2 * _tables.size(), nullptr);// for (int i 0; i _tables.size(); i)// {// Node* pcur _tables[i];// while (pcur)// {// newHT.Insert(pcur-_kv);// pcur pcur-_next;// }// }// _tables.swap(newHT._tables);//}//负载因子1就扩容if (_n _tables.size()){vectorNode* newtables(2 * _tables.size(), nullptr);for (int i 0; i _tables.size(); i){Node* pcur _tables[i];while (pcur){Node* next pcur-_next;//记录下一个节点size_t hashi hs(pcur-_kv.first) % newtables.size();//映射新表的相对位置pcur-_next newtables[hashi];//头插newtables[hashi] pcur;pcur next;}_tables[i] nullptr;}_tables.swap(newtables);}Node* newnode new Node(kv);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}Node* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* pcur _tables[hashi];while (pcur){if (key pcur-_kv.first){return pcur;}pcur pcur-_next;}return nullptr;}bool Erase(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* pcur _tables[hashi];Node* prev nullptr;while (pcur){if (pcur-_kv.first key){if (prev nullptr){_tables[hashi] pcur-_next;}else{prev-_next pcur-_next;}delete pcur;--_n;return true;}prev pcur;pcur pcur-_next;}return false;}private:vectorNode* _tables;size_t _n 0;};
}本篇文章的分享就到这里了如果您觉得在本文有所收获还请留下您的三连支持哦~
