如何建设高大上的网站,中国十大上市装修公司,男女一起做暖暖网站,wordpress文章什么时候收录前言
在学习完map、set这两个由红黑树构成的容器后#xff0c;我们来到了这里hash#xff0c;首先我们要有一个基础的认知——哈希和map与set的仅在使用时的差别区别#xff1a;前者内部的元素没有序#xff0c;而后者有序#xff0c;其它的都相同#xff0c;这里我们可…前言
在学习完map、set这两个由红黑树构成的容器后我们来到了这里hash首先我们要有一个基础的认知——哈希和map与set的仅在使用时的差别区别前者内部的元素没有序而后者有序其它的都相同这里我们可以通过STL标准库对应的unordered_map和unordered_set的两个名字就能看出那hash存在的意义在哪里底层的数据结构又是如何实现的呢 一、存在的意义应用场景
1.1 hash与红黑树map、set
在程序员的第一准则“绝不制造重复的轮子”下明明有了map、set比hash对应容器unordered_map和unordered_set还能排序的容器为啥我们还要添加它呢我们使用时直接忽略有序不是一样用吗
其实前人们也是这样想的所以一开始是没有hash的对应标准容器的。 见上图我们可以看到直到C11标准unordered_map和unordered_set才推出。
1.2 hash的优势
其实hash推出的原因其实我们可以类比List和Vector这两个容器虽然这两容器的应用高度重叠但是这两个容器由于本身的底层的结构不同在面对相同需求时其效率相差甚远所以这两个容器谁也替代不了对方。
hash的底层机构不像map、set的红黑树插入时需要排序旋转、但是由于其结构的特别又保留了查询的效率所以相比红黑树的两个容器hash的优势是大数据的查找。为何有这些优势在下文结构介绍中而红黑树的优势是自带排序和去重还兼顾了查找效率。
二、底层结构
2.1 哈希概念
注
关键码key可以理解为可以代表元素成员变量的唯一代表值就如我们的身份证号一样。哈希函数将元素转化为关键码的方法。
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素 时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即 O(log_2 N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称 为哈希表(Hash Table)(或者称散列表)。
举个生活的栗子大家使用字典时会根据字的拼音字母依次翻到对应页数而每个字母在字典上的映射页数都是已知可查的直接跳到对应页数即可。在下文的进一步解析中我们将以vector来作为“字典”。
当向该结构中
插入元素
根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素
对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功。
例如数据集合{176459}哈希函数设置为hash(key) key % capacity; capacity哈希函数将元素转化为关键码的方法为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。
问题按照上述哈希方式向集合中插入元素44会出现什么问题答案在下个标题
2.2 哈希冲突与哈希函数 ①哈希冲突
对于两个数据元素的关键字k_i和 k_j有k_i ! k_j但有Hash(k_i) Hash(k_j)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢
②哈希函数 引起哈希冲突的一个重要原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有mcapacity个地址时其值域必须在0到m-1之间。哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单(哈希函数需要被对应容器频繁调用不能因为它将hash的效率降下去)
string的哈希函数的算法https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
常见哈希函数 1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
2. 除留余数法--(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址。上面的例子就是
3. 平方取中法 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况
4.数学分析法 利用不同的元素的概率分布情况制定出对应的哈希函数。
例如设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定 相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散 列地址。
数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况
注意
哈希函数设计的越精妙产生哈希冲突的可能性就越低由于不同的哈希函数对于关键码的生成方式不同带来的冲突结果也不同哈希冲突在理论上是不可避免的举几个栗子1、我们将10个成员放入到capacity只有9的哈希表中至少有一个会冲突。 2、由于数据分布集中而hash函数实现没有将集中的元素分开就会导致冲突加重。
既然哈希函数无法从根本的解决哈希冲突那遇到它时该如何解决呢
2.3 哈希冲突解决 解决哈希冲突两种常见的方法是闭散列和开散列哈希桶。
①结构闭散列
也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢
②结构开散列/哈希桶常用 1. 开散列概念 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。 templateclass V
struct HashBucketNode
{HashBucketNode(const V data): _pNext(nullptr), _data(data){}HashBucketNodeV* _pNext;V _data;
};
// 本文所实现的哈希桶中key是唯一的
templateclass V
class HashBucket
{typedef HashBucketNodeV Node;typedef Node* PNode;
public:HashBucket(size_t capacity 3) : _size(0){_ht.resize(GetNextPrime(capacity), nullptr);}// 哈希桶中的元素不能重复PNode* Insert(const V data){// 确认是否需要扩容。。。// _CheckCapacity();// 1. 计算元素所在的桶号size_t bucketNo HashFunc(data);// 2. 检测该元素是否在桶中PNode pCur _ht[bucketNo];while (pCur){if (pCur-_data data)return pCur;pCur pCur-_pNext;}// 3. 插入新元素pCur new Node(data);pCur-_pNext _ht[bucketNo];_ht[bucketNo] pCur;_size;return pCur;}// 删除哈希桶中为data的元素(data不会重复)返回删除元素的下一个节点PNode* Erase(const V data){size_t bucketNo HashFunc(data);PNode pCur _ht[bucketNo];PNode pPrev nullptr, pRet nullptr;while (pCur){if (pCur-_data data){if (pCur _ht[bucketNo])_ht[bucketNo] pCur-_pNext;elsepPrev-_pNext pCur-_pNext;pRet pCur-_pNext;delete pCur;_size--;return pRet;}}return nullptr;}PNode* Find(const V data);size_t Size()const;bool Empty()const;void Clear();bool BucketCount()const;void Swap(HashBucketV, HF ht;~HashBucket();
private:size_t HashFunc(const V data){return data % _ht.capacity();}
private:vectorPNode* _ht;size_t _size; // 哈希表中有效元素的个数
}
③开散列增容 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可 能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希 表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点 再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可 以给哈希表增容。
void _CheckCapacity()
{size_t bucketCount BucketCount();if (_size bucketCount){HashBucketV, HF newHt(bucketCount);for (size_t bucketIdx 0; bucketIdx bucketCount; bucketIdx){PNode pCur _ht[bucketIdx];while (pCur){// 将该节点从原哈希表中拆出来_ht[bucketIdx] pCur-_pNext;// 将该节点插入到新哈希表中size_t bucketNo newHt.HashFunc(pCur-_data);pCur-_pNext newHt._ht[bucketNo];newHt._ht[bucketNo] pCur;pCur _ht[bucketIdx];}}newHt._size _size;this-Swap(newHt);}
}
④ 开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7见下文而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间 1. 探测方式线性探测 比如2.1中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4 因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入
通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突 使用线性探测找到下一个空位置插入新元素 删除
采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素 会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。
线性探测 闭散列的实现
// 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State
{EMPTY, EXIST, DELETE
};// 注意假如实现的哈希表中元素唯一即key相同的元素不再进行插入
// 为了实现简单此哈希表中我们将比较直接与元素绑定在一起
templateclass K, class V
class HashTable
{struct Elem{pairK, V _val;State _state;};
public:HashTable(size_t capacity 3): _ht(capacity), _size(0){for (size_t i 0; i capacity; i)_ht[i]._state EMPTY;}bool Insert(const pairK, V val){// 检测哈希表底层空间是否充足// _CheckCapacity();size_t hashAddr HashFunc(key);// size_t startAddr hashAddr;while (_ht[hashAddr]._state ! EMPTY){if (_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key)return false;hashAddr;if (hashAddr _ht.capacity())hashAddr 0;/*// 转一圈也没有找到注意动态哈希表该种情况可以不用考虑哈希表中元素个数到达一定的数量哈希冲突概率会增大需要扩容来降低哈希冲突因此哈希表中元素是不会存满的if(hashAddr startAddr)return false;*/}// 插入元素_ht[hashAddr]._state EXIST;_ht[hashAddr]._val val;_size;return true;}int Find(const K key){size_t hashAddr HashFunc(key);while (_ht[hashAddr]._state ! EMPTY){if (_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key)return hashAddr;hashAddr;}return hashAddr;}bool Erase(const K key){int index Find(key);if (-1 ! index){_ht[index]._state DELETE;_size;return true;}return false;}size_t Size()const;bool Empty() const;void Swap(HashTableK, V, HF ht);
private:size_t HashFunc(const K key){return key % _ht.capacity();}
private:vectorElem _ht;size_t _size;
};
线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同 关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降 低。如何缓解呢
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是表的大小。 小结哈希unordered_map、unordered_set作为以“映射”的方式储存内容具备了高效的搜索和较低存储代价的特点和强大的红黑树对应的set、map容器做到了再次补充。 我的博客即将同步至腾讯云社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code1omyl741mq270
