网站编程学习,网页设计与制作论文6000,专业建设信息化网站资源,腾讯广告卖东西怎么建设网站unordered系列关联式容器
在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器#xff0c;在查询时效率可达到 l o g 2 N log_2 N log2N#xff0c;即最差情况下需要比较红黑树的高度次#xff0c;当树中的节点非常多时#xff0c;查询效率也不理想。最好的…unordered系列关联式容器
在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到 l o g 2 N log_2 N log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同本文中只对unordered_map和unordered_set进行介绍
unordered_map
unordered_map的简单介绍
unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。它的迭代器至少是前向迭代器。
相比较于map首先他们的底层结构不一样map是红黑树而unordered系列是由哈希的映射关系来实现的他的迭代器是无序的并且是一种单向的迭代器同时unordered也对[]进行了重载综合各种情况来说的话unordered_map比map的性能更好尤其是find的使用
unordered_map的接口说明
接口说明我们在之前的很多stl容器中都演示过这里不做过多的介绍
unordered_map的构造 unordered_map的构容量 unordered_map的迭代器
由于迭代器是单向的所以没有rbegin和rend
unordered_map的元素访问 注意 该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回。
关于哈希桶我们后面会有介绍
unordered_map的查询 注意unordered_map中key是不能重复的因此count函数的返回值最大为1
unordered_map的修改操作 unordered_map的桶操作 unordered_set
关于unordered_set的介绍我就不进行讲解了都差不多
链接: http://www.cplusplus.com/reference/unordered_set/unordered_set/?kwunordered_set
关联式容器的底层结构
我们开头在介绍unordered系列的关联式容器时就有提到之所以他的综合效率比较高是因为其底层使用了哈希结构。下面我们就要正式展开哈希的讲解
哈希的概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。
这个时候我们就会想要是可以不经过比较就能找到对应的元素那岂不是快得很这个时候哈希表就出来了
哈希表是通过某种函数(hashFunc哈希函数)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素的一种顺序存储结构。
当向该结构中插入或者搜索元素时只需要对插入或者搜索的元素的关键码进行相对应的计算就可以得到该元素的适合的位置
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表
举一个例子 数据集合{176459} 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快
但是根据这个方法你能想一想有什么问题吗 如果我插入元素11那么11%10的结果也是1也要存到对应的位置但是这个位置已经有元素1了怎么办呢
哈希冲突
对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
那么该如何解决这个问题呢
先不急我们先把其他的概念了解完
哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间并且哈希函数计算出来的地址能均匀分布在整个空间中
下面我们就对常见的哈希函数进行简单的介绍
常见的哈希函数
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. 折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况
5. 随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法
6. 数学分析法–(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。
注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突
哈希冲突的解决
解决哈希冲突两种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢
线性探测
现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4 因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
1 通过哈希函数获取待插入元素在哈希表中的位置 2 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 那删除呢 如果直接删除计算出来的对应位置的节点就很有可能删除错误比如我要删除44却把4给删除了
为此我们可以标记每个点位采用伪删除法来删除元素
// 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE}; 线性探测的实现
我们用枚举常量标记每一个位置 刚开始将每个位置初始化未EMPTY 插入时先判断该key计算后的对应位置是否为空如果为空就插入不为空就放入下一个不为空的位置删除时直接标记DELETE伪删除即可
enum State { EMPTY, EXIST, DELETE };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;};那么什么时候哈希表会进行扩容呢
我们的AVL树中有一个平衡因子用来判断这棵树是否符合绝对平衡那么哈希表中就有一个载荷因子
载荷因子 填入表中的元素个数 / 散列表的长度
一般情况下如果载荷因子超过0.7就要进行扩容至于为什么我也不知道可能经过了一系列的数学计算吧
而这里的扩容一般都是乘以一个素数也是经过研究的为了方便找素数一办情况下就会有一个素数表 然后定义一个函数取最小的符合条件的素数
size_t GetNextPrime(size_t prime)
{const int PRIMECOUNT 28;static const size_t primeList[PRIMECOUNT] {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t i 0;for (; i PRIMECOUNT; i){if (primeList[i] prime)return primeList[i];}return primeList[i];
}扩容实现如下
void CheckCapacity()
{if (_size * 10 / _ht.capacity() 7){HashTableK, V, HF newHt(GetNextPrime(ht.capacity));for (size_t i 0; i _ht.capacity(); i){if (_ht[i]._state EXIST)newHt.Insert(_ht[i]._val);}Swap(newHt);}
}线性探测优点实现非常简单
线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢
下面我们就来了解一个高效且常用的办法开散列
开散列
开散列概念
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。
这个桶就是我们上面提到的哈希桶
这时我们的这个散列就是一个指针数组了 大家就可以发现每个哈希桶中的元素都是发生了哈希冲突的元素
开散列实现
我们要记住哈希桶中的元素是不能重复的
由于博主能力有限大家仔细对代码进行解读
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; // 哈希表中有效元素的个数
};开散列扩容
桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。
在增容后许多以前冲突的元素可能就不会冲突了所以我们可以根据增容的大小来开辟一个新的开散列然后把原来的开散列的元素重新插入到新的开散列中再用swap函数交换即可
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);}
}好了今天的分享到这里就结束了感谢大家的支持
