怎么让自己的网站通过域名访问不了,虎扑体育网体育,网站一体化建设,建设部网站39文件文章目录 前言一、链地址法概念二、哈希表扩容三、哈希桶插入逻辑四、析构函数五、删除逻辑六、查找七、链地址法代码实现总结 前言
前面我们用开放定址法代码实现了哈希表#xff1a; C#xff1a;揭秘哈希#xff1a;提升查找效率的终极技巧_1
对于开放定址法来说#… 文章目录 前言一、链地址法概念二、哈希表扩容三、哈希桶插入逻辑四、析构函数五、删除逻辑六、查找七、链地址法代码实现总结 前言
前面我们用开放定址法代码实现了哈希表 C揭秘哈希提升查找效率的终极技巧_1
对于开放定址法来说包含以下两种探测插入节点位置方法
线性探测二次探测 但是开放定址法的缺点也很明显开放定址法容易很多数据堆积在一起大大减少了效率。
为了解决上述问题引入了第二种方法实现哈希表 ——链地址法哈希桶法 一、链地址法概念
开放定址法中所有的元素都放到哈希表里。
链地址法中所有的数据不再直接存储在哈希表中。哈希表中存储一个指针没有数据映射到这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面。链地址法也叫做拉链法或者哈希桶。 下⾯演⽰ {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M11的表中。 二、哈希表扩容
开放定址法的负载因子必须小于 1而链地址法的负载因子则没有限制可以大于 1。
负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。
STL 中 unordered_xxx 的最大负载因子基本控制在 1当负载因子大于 1 时会扩容。我们下面的实现也使用这种方式。 也就是说我们期望基本每个节点下面都挂一个桶有那么一两个数据如下图 三、哈希桶插入逻辑 首先如果不需要扩容我们需要将一个节点挂上去因为每一个哈希桶类似于链表而链表的头插效率是十分高的因此我们采用头插。 // 如果不需要扩容size_t hashi hf(kv.first) % _table.size();// 头插Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;其次如果需要扩容的话需要遍历_table取每一个哈希桶的每一个结点重新插入到新表但是这样的话还牵扯到了旧表资源的释放。 因此我们使用顺手牵羊直接将旧表的节点迁过来头插解决资源释放的问题。 // 遍历旧表顺手牵羊把节点牵下来挂到新表for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 头插到新表size_t newhashi hf(cur-_kv.first) % newSize;cur-_next newTable[newhashi];newTable[newhashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}四、析构函数
因为我们vector中存储的是自定义类型因此我们需要显示写析构函数。 遍历整个哈希表删除每一个节点最后将其置空。 ~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}五、删除逻辑
删除就比较简单了它分两种情况 删除的值prev为空——直接删除它把_table[i] cur 删除的值prev不为空——涉及到前后的链接 bool Erase(const K key){HashFunc hf;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}六、查找
这里的查找比较简单遍历整个_table就可以啦~ 七、链地址法代码实现总结
#pragma once
#includevectornamespace hash_bucket
{templateclass Kstruct DefaultHashFunc{size_t operator() (const K key){return (size_t)key;}};templatestruct DefaultHashFuncstring{size_t operator() (const string str){// BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}};templateclass K, class Vstruct HashData{pairK, V _kv;HashDataK, V* _next;HashData(const pairK, V kv): _kv(kv), _next(nullptr){}};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashDataK, V Node;public:HashTable(){_table.resize(10, nullptr);}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}// 仿函数控制HashFunc hf;// 如果需要扩容if (_n _table.size()){size_t newSize _table.size() * 2;vectorNode* newTable;newTable.resize(newSize, nullptr);// 遍历旧表顺手牵羊把节点牵下来挂到新表for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 头插到新表size_t newhashi hf(cur-_kv.first) % newSize;cur-_next newTable[newhashi];newTable[newhashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}// 如果不需要扩容size_t hashi hf(kv.first) % _table.size();// 头插Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* Find(const K key){HashFunc hf;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){HashFunc hf;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}void Print(){for (size_t i 0; i _table.size(); i){printf([%d]-, i);Node* cur _table[i];while (cur){cout cur-_kv.first : cur-_kv.second -;cur cur-_next;}printf(NULL\n);}cout endl;}private:vectorNode* _table; // 指针数组size_t _n 0; // 存储了多少个有效数据};
}到这里就结束啦创作不易如果对您有帮助的话麻烦给一个一键三连谢谢各位大佬~
