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

erp .net网站开发重庆森林电影完整版

news 2025/7/15 0:35:51
erp .net网站开发,重庆森林电影完整版,网站建设项目技术,wordpress 为分类定模板目录 1. 哈希概念 2.哈希冲突 3.哈希函数 4.哈希冲突解决 4.1闭散列 4.1.1何时扩容？如何扩容？ 4.1.2线性探测 4.1.3二次探测 4.2开散列(哈希桶) 4.2.1概念 4.2.2开散列增容 1. 哈希概念 顺序结构以及平衡树中，元素关键码与其存储…

目录

1. 哈希概念

2.哈希冲突

3.哈希函数

4.哈希冲突解决

4.1闭散列

4.1.1何时扩容？如何扩容？

4.1.2线性探测

4.1.3二次探测

4.2开散列(哈希桶)

4.2.1概念

4.2.2开散列增容

 

1. 哈希概念

  • 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(logN)，搜索的效率取决于搜索过程中元素的比较次数
  • 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素
  • 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素
  • 当向该结构中：

                1.插入元素

                            根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

                2.搜索元素

                            对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键                                码相等，则搜索成功

                 3.该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)                     (或者称散列表)

2.哈希冲突

对于两个数据元素的关键字k_i和k_j(i != j)，有k_i != k_j，但有：Hash(k_i) == Hash(k_j)

  • 即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为 哈希冲突 或 哈希碰撞
  • 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

3.哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理

哈希函数设计原则：

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

常见哈希函数：

1.直接定址法 – (常用) --> 不存在哈希冲突

  •  取关键字的某个线性函数为散列地址：Hash(Key)= A*Key + B
  •  优点：简单、均匀
  •   缺点：需要事先知道关键字的分布情况
  •   使用场景：适合查找比较小且连续的情况

2.除留余数法 – (常用) --> 存在哈希冲突，重点解决哈希冲突

  • 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数
  • 按照哈希函数：Hash(key) = key% p (p<=m)，将关键码转换成哈希地址

3.平方取中法 – (了解)

  • 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
  • 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
  • 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4.折叠法 – (了解)

  • 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
    • 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5.随机数法 – (了解)

  • 选择一个随机函数，取关键字的随机函数值为它的哈希地址
  • 即H(key) = random(key),其中 random为随机数函数

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

4.哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

4.1闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

4.1.1何时扩容？如何扩容？

1.散列表的载荷因子定义为：α = 填入表中的元素个数 / 散列表的长度

  • α越大，表中元素越多，产生冲突概率越大
  • α越小，表明元素越少，产生冲突概率越小
  • 一般不要超过0.7~0.8

2.什么时候扩容？ --> 负载因子到一个基准值就扩容

  • 基准值越大，冲突越多，效率越低，空间利用率越高
  • 基准值越小，冲突越少，效率越高，空间利用率越低
4.1.2线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

1.插入

  • 通过哈希函数获取待插入元素在哈希表中的位置

  • 如果该位置中没有元素则直接插入新元素

  • 如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素

2.删除

  • 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素，会影响其他元素的搜索
  • 比如删除元素4，如果直接删除掉，44查找起来可能会受影响
  • 因此线性探测采用标记的伪删除法来删除一个元素
4.1.3二次探测

1.线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找

2.因此二次探测为了避免该问题，找下一个空位置的方法为：

  • H_i = (H_0 + i^2 ) % m 或者 H_i = (H_0 - i^2 ) % m (i = 1,2,3**…)**
  • H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小

 3.研究表明：

  • 当表的长度为质数且表载荷因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次
  • 因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

namespace CH1
{enum STATE{EXIST,EMPTY,DELETE};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){int sum = 0;for (auto& x : str){sum *= 131;sum += x;}return sum;}};template<class K, class V>struct HashDate{pair<K, V> _kv;STATE _state = EMPTY;};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public://构造函数HashTable(){_table.resize(10);}//插入bool insert(const pair<K, V>& kv){//负载因子到了就扩容if ((double)n / _table.size() >= 0.7){size_t newsize = _table.size() * 2;HashTable<K, V> newtable;//开创一个新表，将原来的数据，都移过来，并且重新赋予位置newtable._table.resize(newsize);//将原来的数据移过来for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newtable.insert(_table[i]._kv);}}//两表交换，新创建的表，出了作用域会被销毁_table.swap(newtable._table);}HashFunc hf;// 哈希地址计算size_t hashnum = hf(kv.first) % _table.size();while (_table[hashnum]._state == EXIST)//找到空{hashnum += 1;hashnum %= _table.size();}_table[hashnum]._kv = kv;_table[hashnum]._state = EXIST;++n;return true;}HashDate<const K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key){return (HashDate<const K, V>*) & _table[hashi];}hashi++;hashi %= _table.size();}return nullptr;}bool erase(const K& key){HashDate<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;n--;}else{return false;}}void printf(){for (size_t i = 0; i < _table.size(); i++){cout << _table[i]._kv.first << " ";}}private:vector<HashDate<K, V>> _table;size_t n = 0;//记录数据有效数据};
}

4.2开散列(哈希桶)

4.2.1概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

4.2.2开散列增容
  • 桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？
  • 开散列最好的情况是：每个哈希桶中刚好挂一个节点， 再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

4.2.3开散列思考

  • 只能存储key为整形的元素，其他类型怎么解决？

  • 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法：：利用仿函数

  • 除留余数法，最好模一个素数，如何每次快速取一个类似两倍关系的素数？‘

4.2.4开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销

事实上：

  • 由于开放定址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7
  • 而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间
namespace CH2
{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){int sum = 0;for (auto& x : str){sum *= 131;sum += x;}return sum;}};template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}};template<class K, class V, class HashFunc= DefaultHashFunc<K>>class HashTable{typedef HashNode<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){HashFunc ht;//扩容if (_n == _table.size()){size_t newhashi = 2 * _table.size();vector<Node*> newtable;newtable.resize(newhashi,nullptr);for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = ht(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = ht(kv.first) % _table.size();Node* cur = new Node(kv);cur->_next = _table[hashi];_table[hashi] = cur;_n++;return true;}Node* Find(const K& key){HashFunc ht;size_t hashi = ht(key) % _table.size();Node* cur = _table[hashi];while (cur){Node* next = cur->_next;if (cur->_kv.first == key){return cur;}cur = next;}return nullptr;}bool erase(const K& key){HashFunc ht;size_t hashi = ht(key) % _table.size();Node* cur = _table[hashi];Node* prve = nullptr;while (cur){//头删//中间删if (ht(cur->_kv.first) == key){if (prve == nullptr){_table[hashi] = cur->_next;}else{prve->_next = cur->_next;}delete cur;return true;}prve = cur;cur = cur->_next;}return false;}void print(){for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];printf("%zd->", i);while (cur){cout << cur->_kv.first << "->";cur = cur->_next;}cout << "Null" << endl;}}private:vector<Node*> _table;//创建一个数组，数组中的每一个成员都是节点size_t _n = 0;//记录有效个数};
}

http://www.hengruixuexiao.com/news/45870.html

相关文章：

  • 怎么随便搞个网站百度推广seo
  • 影视怎么建设网站网页制作培训网站
  • 网站建设进度计划seo文案范例
  • 北京医疗网站建设公司排名广州优化seo
  • 网站建设管理员搜索引擎优化seo专员
  • 做ppt的兼职网站有哪些营销型网站的公司
  • dw可以做有后台的网站么最新的销售平台
  • 资料网站怎么做昆明百度推广开户费用
  • 网站开发接入本地天地图短视频营销的发展趋势
  • 毕节网站怎么做seo专注于品牌营销服务
  • 南宁网站建设liluokj搜索引擎技术
  • 做网站打电话话术西安百度seo
  • 设计广告网站宜兴百度推广
  • 赣州朝扬网络科技有限公司seo是一种利用搜索引擎
  • 长治网站制作平台网络优化工程师招聘信息
  • 域名建议网站关键词全网搜索
  • 如何自己开一个网站网络营销师培训
  • 深圳最好的网站开发公司电话千锋教育学费多少
  • 北京网站seo策划百度搜索结果
  • 怎么做自己的发卡网站6商务软文写作
  • 网上做网页网站任务赚钱查淘宝关键词排名软件有哪些
  • wordpress 网站变慢优化大师优化项目有
  • 做网站职业咋样哪个平台可以免费打广告
  • 自己做网站兼职小程序开发公司
  • 能免费做网站网站及推广
  • 重庆网站建设找承越国际新闻最新消息今天 新闻
  • 佛山网站建设哪家好宣传推广方案怎么写
  • 网站备案注销申请书seo顾问是什么
  • 大连企业网站阿里云com域名注册
  • CP网站开发制作H5网络广告设计