当前位置: 首页 > news >正文

一个门户网站需要多大的空间谷歌seo排名

一个门户网站需要多大的空间,谷歌seo排名,全国疫情中高风险地区,网站导航怎么做的文章目录 前言一、链地址法概念二、哈希表扩容三、哈希桶插入逻辑四、析构函数五、删除逻辑六、查找七、链地址法代码实现总结 前言 前面我们用开放定址法代码实现了哈希表: C:揭秘哈希:提升查找效率的终极技巧_1 对于开放定址法来说&#…

在这里插入图片描述

文章目录

  • 前言
  • 一、链地址法概念
  • 二、哈希表扩容
  • 三、哈希桶插入逻辑
  • 四、析构函数
  • 五、删除逻辑
  • 六、查找
  • 七、链地址法代码实现总结


前言

前面我们用开放定址法代码实现了哈希表:
C++:揭秘哈希:提升查找效率的终极技巧_1

对于开放定址法来说,包含以下两种探测插入节点位置方法:

  1. 线性探测
  2. 二次探测

在这里插入图片描述

但是开放定址法的缺点也很明显,开放定址法容易很多数据堆积在一起,大大减少了效率。

为了解决上述问题,引入了第二种方法实现哈希表
——链地址法(哈希桶法)


一、链地址法概念

开放定址法中,所有的元素都放到哈希表里。

链地址法中,所有的数据不再直接存储在哈希表中。哈希表中存储一个指针,没有数据映射到这个位置时,这个指针为空;有多个数据映射到这个位置时,我们把这些冲突的数据链接成一个链表,挂在哈希表这个位置下面。链地址法也叫做拉链法或者哈希桶。

下⾯演⽰ {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中。

在这里插入图片描述


二、哈希表扩容

开放定址法的负载因子必须小于 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;}}

五、删除逻辑

删除就比较简单了,它分两种情况:

  1. 删除的值prev为空——直接删除它,把_table[i] = cur

在这里插入图片描述

  1. 删除的值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
#include<vector>namespace hash_bucket
{template<class K>struct DefaultHashFunc{size_t operator() (const K& key){return (size_t)key;}};template<>struct DefaultHashFunc<string>{size_t operator() (const string& str){// BKDRsize_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}};template<class K, class V>struct HashData{pair<K, V> _kv;HashData<K, V>* _next;HashData(const pair<K, V>& kv): _kv(kv), _next(nullptr){}};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashData<K, 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 pair<K, V>& kv){if (Find(kv.first)){return false;}// 仿函数控制HashFunc hf;// 如果需要扩容if (_n == _table.size()){size_t newSize = _table.size() * 2;vector<Node*> 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:vector<Node*> _table;     // 指针数组size_t _n = 0;            // 存储了多少个有效数据};
}

到这里就结束啦,创作不易,如果对您有帮助的话,麻烦给一个一键三连,谢谢各位大佬~

在这里插入图片描述

http://www.dinnco.com/news/32358.html

相关文章:

  • 做网站的相关教程百度app首页
  • pc网站开发获取位置郑州seo联系搜点网络效果好
  • 湘潭网站建设 要选磐石网络百度广告开户流程
  • webqq网页版广州优化网站排名
  • 重庆软件开发工资一般多少夫唯seo
  • wordpress 评分插件廊坊优化外包
  • 怎么做自动下单网站市场营销比较好写的论文题目
  • 淘宝网站怎么做的好看免费域名怎么注册
  • 石家庄做网站需要多少钱代写企业软文
  • 镇平网站建设百度seo权重
  • 网站特效 站长互联网广告价格
  • 牡丹江林口县建设局网站推广软文范文800字
  • 店铺推广软文范文长春seo关键词排名
  • 网站美工设计广东新闻今日最新闻
  • 如何免费建设网站comseo 360
  • 茶叶公司网站模板微博推广费用
  • 帝国网站地图模板网站策划运营
  • 免费软件下载官方网站我想做百度推广
  • 有哪些是做二手的网站南昌seo代理商
  • 网站制作还花钱google搜索关键词
  • 东莞南城网站建设价格营销型网站建站
  • 大连比较好的的网站建设公司百度的电话人工客服电话
  • 网站开发需要数据库技术网络广告有哪些
  • 湘潭响塘乡建设局网站市场推广是做什么的
  • 个人可以做慈善网站吗百度新闻首页新闻全文
  • 做视频背景音乐网站推广普通话的意义论文
  • wordpress怎么删除文章网站推广优化排名
  • 手机app手机网站开发seo公司推荐推广平台
  • 高明网站建设报价百度推广入口官网
  • 做家装的网站有哪些内容百度网站快速排名公司