网站在建设中是什么意思,一级a做爰片i免费网站,泰州网站制作网站,网站建立前期调查文章目录前言一、unordered系列关联式容器1. unordered_map2. unordered_set二、哈希1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决方法三、模拟实现unordered系列容器1. 哈希表的改造2. 模拟实现 unordered_set3. 模拟实现 unordered_map前言 在C11中#xff0c;STL又提…
文章目录前言一、unordered系列关联式容器1. unordered_map2. unordered_set二、哈希1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决方法三、模拟实现unordered系列容器1. 哈希表的改造2. 模拟实现 unordered_set3. 模拟实现 unordered_map前言 在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同unordered系列的关联式容器的底层结构采用哈希结构。 map/set的遍历是有序的而unordered系列容器遍历是无序的。map/set是双向迭代器而unordered系列容器只支持单向迭代器。但是当对大量数据进行增删改查时unordered系列容器的效率更高尤其是查找的效率。
一、unordered系列关联式容器
1. unordered_map
构造
函数声明功能介绍unordered_map()构造空的unordered_map对象容量
函数声明功能介绍bool empty() const检测unordered_map是否为空size_t size() const获取unordered_map的有效元素个数迭代器
函数声明功能介绍begin返回unordered_map第一个元素的迭代器end返回unordered_map最后一个元素下一个位置的迭代器cbegin返回unordered_map第一个元素的const迭代器cend返回unordered_map最后一个元素下一个位置的const迭代器元素访问
函数声明功能介绍operator[]返回与key对应的value没有一个默认值查询
函数声明功能介绍iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为key的键值对的个数修改
函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered_map)交换两个容器中的元素桶操作
函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号2. unordered_set unordered_set的函数基本上与unordered_map类似故不在说明。另外在使用方面unordered系列的容器与map/set容器也基本类似。可以说除了底层结构和unordered系列操作哈希桶外两者没有区别。
二、哈希
1. 哈希概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(log2Nlog_2 Nlog2N)搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法是不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。 哈希方法 插入元素时根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素时对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。 该方式即为哈希/散列方法哈希方法中使用的转换函数称为哈希/散列函数构造出来的结构称为哈希表(Hash Table)/称散列表。 2. 哈希冲突 对于两个数据元素的关键字kik_iki和 kjk_jkj(i ! j)有kik_iki ! kjk_jkj但有Hash(kik_iki) Hash(kjk_jkj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。引起哈希冲突的一个原因可能是哈希函数设计不够合理。哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。 3. 哈希函数
1直接定址法 取关键字的某个线性函数为散列地址HashKey A*Key B 该方法优点是简单、均匀不存在哈希冲突缺点是需要事先知道关键字的分布情况适合查找比较小且连续的情况。 2除留余数法 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p (pm),将关键码转换成哈希地址。 3其他方法 哈希函数还有采用平方取中法、折叠法、随机数法、数学分析法等等但是不常用常用的还是前两种方法。 4. 哈希冲突解决方法 解决哈希冲突两种常见的方法是闭散列和开散列。 1闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 寻找下一个空位置可以使用线性探测和二次探测。 线性探测 线性探测是从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入时通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。如图所示44与4发生冲突使用线性探测法插入44到哈希表中位置为8的空位置。 给定一个负载因子为填入表中的元素个数/散列表的长度负载因子越大冲突概率越大效率越低空间利用率越高负载因子越小冲突概率越小效率越高空间利用率越低。 删除时采用闭散列处理哈希冲突不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为HiH_iHi (H0H_0H0 i2i^2i2 )% m, 其中i 1,2,3… H0H_0H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小。 代码实现
namespace CloseHash
{//哈希表每个空间给个标记EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除enum State{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};//使用仿函数将key转换为无符号的整形方便插入时取模计算位置templateclass K struct HashFunc{size_t operator()(const K key){return (size_t)key; }};// 模板特化 支持string类型转换为无符号整形templatestruct HashFuncstring{// BKDR算法size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}};templateclass K, class V, class Hash HashFuncKclass HashTable{public:bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子到了就扩容if (_tables.size() 0 || 10 * _size / _tables.size() 7) // 扩容{size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V, Hash newHT; //这样可以复用insert函数newHT._tables.resize(newSize);// 旧表的数据映射到新表for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}//使用仿函数将key转换为无符号的整形Hash hash;size_t hashi hash(kv.first) % _tables.size();// 线性探测while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_size; 二次探测//Hash hash;//size_t start hash(kv.first) % _tables.size();//size_t i 0;//size_t hashi start;//while (_tables[hashi]._state EXIST)//{// i;// hashi start i*i;// hashi % _tables.size();//}//_tables[hashi]._kv kv;//_tables[hashi]._state EXIST;//_size;return true;}HashDataK, V* Find(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t start hash(key) % _tables.size();size_t hashi start;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();if (hashi start){break;}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;--_size;return true;}else{return false;}}void Print(){for (size_t i 0; i _tables.size(); i){if (_tables[i]._state EXIST){printf([%d:%d] , i, _tables[i]._kv.first);}else{printf([%d:*] , i);}}cout endl;}private:vectorHashDataK, V _tables;size_t _size 0; // 存储多少个有效数据};
}2开散列 开散列法又叫链地址法/开链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 如图所示开散列中每个桶中放的都是发生哈希冲突的元素。 开散列增容 开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 哈希桶实现开散列
//使用仿函数将key转换为无符号的整形方便插入时取模计算位置
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{// BKDRsize_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};namespace Bucket
{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 Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}// 如果hash的size是素数可以减少冲突inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes 28;static const size_t __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (size_t i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return -1;}bool Insert(const pairK, V kv){// 去重if (Find(kv.first)){return false;}Hash hash;// 负载因子到1就扩容if (_size _tables.size()){//size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;vectorNode* newTables;//newTables.resize(newSize, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr); //扩容时resize素数表中数据的大小// 旧表中节点移动映射新表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hash(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hash(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_size;return true;}Node* Find(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){if (_tables.size() 0){return false;}Hash hash;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){// 1、头删// 2、中间删if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}size_t Size(){return _size;}// 表的长度size_t TablesSize(){return _tables.size();}// 桶的个数size_t BucketNum(){size_t num 0;for (size_t i 0; i _tables.size(); i){if (_tables[i]){num;}}return num;}size_t MaxBucketLenth(){size_t maxLen 0;for (size_t i 0; i _tables.size(); i){size_t len 0;Node* cur _tables[i];while (cur){len;cur cur-_next;}if (len maxLen){maxLen len;}}return maxLen;}private:vectorNode* _tables;size_t _size 0; // 存储有效数据个数};
}开散列与闭散列比较 由于闭散列法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子而表项所占空间又比指针大的多所以使用开散列法反而比闭散列法节省存储空间。 三、模拟实现unordered系列容器
1. 哈希表的改造 哈希表的改造时对模板参数列表的改造增加迭代器操作
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 特化
template
struct HashFuncstring
{// BKDRsize_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};namespace Bucket
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};// 前置声明templateclass K, class T, class Hash, class KeyOfTclass HashTable;//迭代器templateclass K, class T, class Hash, class KeyOfTstruct __HashIterator{typedef HashNodeT Node;typedef HashTableK, T, Hash, KeyOfT HT;typedef __HashIteratorK, T, Hash, KeyOfT Self;Node* _node;HT* _pht;__HashIterator(Node* node, HT* pht):_node(node), _pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next){// 当前桶中迭代_node _node-_next;}else{// 找下一个桶Hash hash;KeyOfT kot;size_t i hash(kot(_node-_data)) % _pht-_tables.size();i;for (; i _pht-_tables.size(); i){if (_pht-_tables[i]){_node _pht-_tables[i];break;}}// 说明后面没有有数据的桶了if (i _pht-_tables.size()){_node nullptr;}}return *this;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}};templateclass K, class T, class Hash, class KeyOfTclass HashTable{typedef HashNodeT Node;templateclass K, class T, class Hash, class KeyOfTfriend struct __HashIterator;public:typedef __HashIteratorK, T, Hash, KeyOfT iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes 28;static const size_t __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (size_t i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return -1;}pairiterator, bool Insert(const T data){Hash hash;KeyOfT kot;// 去重iterator ret Find(kot(data));if (ret ! end()){return make_pair(ret, false);}// 负载因子到1就扩容if (_size _tables.size()){//size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;vectorNode* newTables;//newTables.resize(newSize, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr);// 旧表中节点移动映射新表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hash(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hash(kot(data)) % _tables.size();// 头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_size;return make_pair(iterator(newnode, this), true);}iterator Find(const K key){if (_tables.size() 0){return end();}Hash hash;KeyOfT kot;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return end();}bool Erase(const K key){if (_tables.size() 0){return false;}Hash hash;KeyOfT kot;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){// 1、头删// 2、中间删if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}size_t Size(){return _size;}// 表的长度size_t TablesSize(){return _tables.size();}// 桶的个数size_t BucketNum(){size_t num 0;for (size_t i 0; i _tables.size(); i){if (_tables[i]){num;}}return num;}size_t MaxBucketLenth(){size_t maxLen 0;for (size_t i 0; i _tables.size(); i){size_t len 0;Node* cur _tables[i];while (cur){len;cur cur-_next;}//if (len 0)//printf([%d]号桶长度:%d\n, i, len);if (len maxLen){maxLen len;}}return maxLen;}private:vectorNode* _tables;size_t _size 0; // 存储有效数据个数};
}2. 模拟实现 unordered_set
namespace Jared
{templateclass K, class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename Bucket::HashTableK, K, Hash, SetKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}private:Bucket::HashTableK, K, Hash, SetKeyOfT _ht;};
}3. 模拟实现 unordered_map
namespace Jared
{templateclass K, class V, class Hash HashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename Bucket::HashTableK, pairK, V, Hash, MapKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool Insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}private:Bucket::HashTableK, pairK, V, Hash, MapKeyOfT _ht;};
}
