辽阳建设网站公司报价,wordpress 2万条就卡,官方网站建设有限公司,专注服务于站长和网站的信息平台.目录
1. 哈希概念
2.哈希冲突
3.哈希函数
4.哈希冲突解决
4.1闭散列
4.1.1何时扩容#xff1f;如何扩容#xff1f;
4.1.2线性探测
4.1.3二次探测
4.2开散列(哈希桶)
4.2.1概念
4.2.2开散列增容 1. 哈希概念
顺序结构以及平衡树中#xff0c;元素关键码与其存储…目录
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 (pm)将关键码转换成哈希地址 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};templateclass Kstruct DefaultHashFunc{size_t operator()(const K key){return (size_t)key;}};template//特化struct DefaultHashFuncstring{size_t operator()(const string str){int sum 0;for (auto x : str){sum * 131;sum x;}return sum;}};templateclass K, class Vstruct HashDate{pairK, V _kv;STATE _state EMPTY;};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{public://构造函数HashTable(){_table.resize(10);}//插入bool insert(const pairK, V kv){//负载因子到了就扩容if ((double)n / _table.size() 0.7){size_t newsize _table.size() * 2;HashTableK, 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;}HashDateconst 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 (HashDateconst K, V*) _table[hashi];}hashi;hashi % _table.size();}return nullptr;}bool erase(const K key){HashDateK, 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:vectorHashDateK, 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
{templateclass Kstruct DefaultHashFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct DefaultHashFuncstring{size_t operator()(const string str){int sum 0;for (auto x : str){sum * 131;sum x;}return sum;}};templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, 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){HashFunc ht;//扩容if (_n _table.size()){size_t newhashi 2 * _table.size();vectorNode* 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:vectorNode* _table;//创建一个数组数组中的每一个成员都是节点size_t _n 0;//记录有效个数};
}
