淘宝的网站怎么做的好处,网络营销理论包括哪些,一个网站如何做双语,为什么建网站目录
一、unordered_map
1.1、unordered_map的特点
1.2、unordered_map和map的区别
二、unordered_set
2.1、unordered_set的特点
2.2、unordered_set和set的区别
三、哈系桶的改造
3.1 结构设置
3.2 构造函数和析构函数
3.3 数据插入
3.4 数据查找
3.5 数据删除
…目录
一、unordered_map
1.1、unordered_map的特点
1.2、unordered_map和map的区别
二、unordered_set
2.1、unordered_set的特点
2.2、unordered_set和set的区别
三、哈系桶的改造
3.1 结构设置
3.2 构造函数和析构函数
3.3 数据插入
3.4 数据查找
3.5 数据删除
3.6 迭代器实现
3.7、友元声明
编辑
四、unordered_map封装
五、unordered_set封装
六、哈希表 一、unordered_map
unordered_map其实就是与map相对应的一个容器。学过map就知道map的底层是一个红黑树通过中序遍历的方式可以以有序的方式遍历整棵树。而unordered_map正如它的名字一样它的数据存储其实是无序的这也和它底层所使用的哈希结构有关。而在其他功能上unordered_map和map基本上就是一致的。
1.1、unordered_map的特点 1unordered_map是用于存储key, value键值对的关联式容器它允许通过key快速的索引到对应的value。 2在内部unorder_map没有对key, value按照任何特定的顺序排序为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的key, value键值对放在相同的桶中。 3unordered_map容器的搜索效率比map快但它在遍历元素自己的范围迭代方面效率就比较低。 4它的迭代器只能向前迭代不支持反向迭代。 1.2、unordered_map和map的区别 从大结构上看unordered_map和map的模板其实没有太大差距。学习了map和set我们就应该知道map是通过T来告诉红黑树要构造的树的存储数据类型的unordered_map也是一样的但是它的参数中多了Hash和Pred两个参数这两个参数都传了仿函数主要和哈希结构有关。这里先不过多讲解
二、unordered_set
unordered_set其实也是一样的从功能上来看和set并没有什么区别只是由于地层数据结构的不同导致unordered_set的数据是无序的但是查找效率非常高。
2.1、unordered_set的特点 无序性unordered_set中的元素没有特定的顺序不会根据插入的顺序或者元素的值进行排序。 唯一性unordered_set中的元素是唯一的不允许重复的元素。 快速查找unordered_set使用哈希表实现可以在平均常数时间内进行查找操作即使在大型数据集上也能保持高效。 插入和删除效率高unordered_set的插入和删除操作的平均时间复杂度为常数时间即O(1)。 高效的空间利用unordered_set使用哈希表来存储元素不会浪费额外的空间。 不支持修改操作由于unordered_set中的元素是唯一的不支持直接修改元素的值需要先删除旧值再插入新值。 迭代器失效在进行插入和删除 2.2、unordered_set和set的区别 很明显unordered_set相较于set多了Hash和Pred两个参数。这两个参数都是传了仿函数和unordered_map与map之间的关系都是一样的这里先不过多讲解。
三、哈系桶的改造
3.1 结构设置
首先这里实现的哈希桶需要能够同时支持unordered_map和unordered_set的调用。因此在传入的数据中就需要有一个T来标识传入的数据类型。同时还需要有Hash函数和KeyOfT来分别对传入的数据转换为整形和获取传入数据的key值主要是提供给使用了KV模型的数据。
我们还要知道哈希桶其实是保存在一个顺序表中的每个下标对应的位置上都是桶的头节点每个桶中的数据以单链表的方式链接起来。因此我们就需要一个vector来存储结构体指针这个结构体中包含了当前节点存储的数据和下一个节点的位置。当然还有有一个_n来记录顺序表中数据的个数。
namespace BucketHash//哈希桶
{//哈希桶内的每个节点/templateclass Tstruct HashNode{T _data;//存储数据HashNodeT* _next;//指向下一个节点HashNode(const T data): _data(data), _next(nullptr){}};templateclass K, class T, class Hash, class KeyOfTclass HashBucket{templateclass K, class T, class Hash, class KeyOfTfriend struct HashIterator;//友元声明让迭代器可以访问哈希桶的私有成员typedef HashNodeT Node;public:typedef HashIteratorK, T, Hash, KeyOfT iterator;private:vectorNode* _bucket;//存储数据的指针数组size_t _n;};
}
在类的模板参数中Hash为将数据转化为整形的仿函数KeyOfT是返回键值的仿函数。
注意上面的代码中有一个迭代器的重命名和迭代器结构体的友元声明。重命名是为了方便后续的使用。友元声明则和迭代器的实现有关这里先不过多讲解。
3.2 构造函数和析构函数
注意这里没有实现拷贝构造。并不是不需要实现实际上虽然哈希桶内的成员是自定义类型的会去调自己的拷贝构造但是这里只会进行浅拷贝不满足需要。如果有需要可以自己实现拷贝构造实现起来也很简单。
HashBucket():_n(0)
{_bucket.resize(10);//构建时默认开10个空间
}~HashBucket()//析构函数
{for (auto cur : _bucket){while (cur){Node* prev cur;cur cur-_next;delete prev;prev nullptr;}}
}
3.3 数据插入
insert函数返回的是pairiterator, bool这是为了后续实现 [ ] 重载做准备。
在插入时首先要先查看哈希桶中是否存在相同键值存在就直接返回当前位置。第二步就是要查看哈希桶中的元素个数与哈希桶的容量之间的负载因子如果等于1就需要进行扩容。第三步则是开始插入节点。先找到映射位置然后新建一个节点连接到对应的数组下标的空间中即可
pairiterator, bool insert(const T data)//插入数据
{KeyOfT kt;iterator it find(kt(data));if (it ! end())//不允许数据重复找到相同的返回return make_pair(it, false);if (_bucket.size() _n)//负载因子设置为1超过就扩容{vectorNode* newbucket;//这种方式就无需再开空间拷贝节点newbucket.resize(NextPrime(_bucket.size()));//开一个素数大小的空间for (size_t i 0; i _bucket.size(); i){Node* cur _bucket[i];while (cur){Node* next cur-_next;size_t hashi Hash()(kt(cur-_data)) % newbucket.size();//找映射位置cur-_next newbucket[hashi];//头插到新哈希表newbucket[hashi] cur;cur next;}_bucket[i] nullptr;//将原哈希表中的指针置为空}_bucket.swap(newbucket);//将newbucket中的节点全部交换给_bucket}Hash knt;size_t hashi knt(kt(data)) % _bucket.size();//找映射位置Node* newnode new Node(data);newnode-_next _bucket[hashi];//头插让插入的节点的下一个指针指向头节点_bucket[hashi] newnode;//让头节点指向插入的节点_n;return make_pair(iterator(newnode, this), true);
}
3.4 数据查找
查找数据很简单。先通过hash函数计算出要查找的数据键值所对应的位置如果对应的位置上存储的是空说明不存在直接返回。如果不为空则比对键值相同返回不相同向下找直到为空。
iterator find(const K key)//查找
{size_t pos Hash()(key) % _bucket.size();//找映射位置 Node* cur _bucket[pos];while (cur){if (KeyOfT()(cur-_data) key)return iterator(cur, this);elsecur cur-_next;}return end();
}
3.5 数据删除
哈希桶与哈希表不同要删除数据时不能使用find函数搜索。因为哈希桶中的数据是用单链表链接起来的用find就无法知道节点的父节点进而无法链接链表。
因此在删除时首先要调用hash函数获取关键码根据关键码蛆对应位置上找。如果该位置存的数据为空则表示不存在返回如果不为空就比较键值相同为找到删除不同就继续向下找直到为空。
bool erase(const K key)//删除
{size_t hashi Hash()(key) % _bucket.size();//找映射位置Node* cur _bucket[hashi];Node* prev nullptr;while (cur){if (KeyOfT()(cur-_data) key){if (cur _bucket[hashi])_bucket[hashi] cur-_next;elseprev-_next cur-_next;delete cur;--_n;cur nullptr;return true;}else{prev cur;cur cur-_next;}}return false;
}
3.6 迭代器实现
哈希桶中的迭代器实现方式比较复杂。要使用迭代器首先就要有能够遍历哈希桶的手段。因此为了便于遍历迭代器的结构体中首先要有哈希桶的指针。当然迭代器的结构体中还需要有一个数据的指针用于初始化迭代器获取对应位置上的内容。
要遍历哈希桶很简单和find的逻辑差不多。直接判断当前节点是否为空不为空则返回为空就说明当前下标对应的位置上已经没有数据了就调用hash函数获取该节点的关键码。关键码走向下一个下标不为空则返回为空则继续走直到找到不为空的位置或结束。 如上图所示一个哈希表其中有四个哈希桶迭代器是it。 it操作 如果it不是某个桶的最后一个元素则it指向下一个节点。如果it是桶的最后一个元素则it指向下一个桶的头节点。 templateclass K, class T, class Hash, class KeyOfT
class HashBucket;//前置声明因为迭代器中使用了HashBucket的模板但是迭代器在它之前无法找到所以要前置声明templateclass K, class T, class Hash, class KeyOfT
struct HashIterator
{typedef HashNodeT Node;typedef HashIteratorK, T, Hash, KeyOfT Self;typedef HashBucketK, T, Hash, KeyOfT HB;//将哈希桶传进来HashIterator(Node* node, HB* hb):_node(node),_hb(hb){}T operator*()//解引用{return _node-_data;}T* operator-()//运算符-重载{return _node-_data;}bool operator!(const Self sl) const//判断是否相等{return _node ! sl._node;}Self operator()//运算符重载{if (_node-_next)//节点的下一个位置不为空{_node _node-_next;}else//节点的下一个位置为空说明该位置上已经没有值找下一个不为空的桶节点{KeyOfT kt;size_t hashi Hash()(kt(_node-_data)) % _hb-_bucket.size();hashi;while (hashi _hb-_bucket.size())//当前位置小于桶的数量{if (_hb-_bucket[hashi])//如果hashi位置上不为空则修改_node的值{_node _hb-_bucket[hashi];break;}elsehashi;}if (hashi _hb-_bucket.size())//如果hashi的位置与桶的数量相当说明没有找到_node nullptr;}return *this;}Node* _node;//节点指针HB* _hb;//哈希桶的指针
};
注意因为模板是向上寻找的在迭代器的类模板中使用了哈希桶的类模板所以如果迭代器类模板在哈希桶类模板之上就需要进行类声明让迭代器类模板能找到哈希桶类模板的位置。反之亦然。
注意因为迭代器中传入了哈希桶要对哈希桶进行遍历。但因为哈希桶中的成员变量都被设置为了私有所以可以将迭代器声明为哈希桶的友元类也可以单独提供一个获取哈希桶指针的函数。
有了迭代器的类模板后哈希桶的迭代器实现起来就很轻松了。
iterator begin()
{for (size_t i 0; i _bucket.size(); i){if (_bucket[i]){return iterator(_bucket[i], this);}}return iterator(nullptr, this);
}iterator end()
{return iterator(nullptr, this);
}
注意哈希桶的begin要返回的是第一个不为空的桶而不是第一个节点。
3.7、友元声明
在迭代器的时候会使用到哈希表指针哈希表指针又会使用到HashTable中的_tables。
HashTable中的_tables是私有成员在类外是不能访问的。
解决这个问题可以在HashTable中写一个公有的访问函数也可以采用友元本喵这里就是使用的友元的方式。
类模板的友元声明需要写模板参数在类名前面加friend关键字如上图绿色框中所示。
迭代器中的其他操作如解引用箭头以及相等等运算符的重载本喵就不再详细介绍了后面本喵会附源码直接看代码即可。 四、unordered_map封装
#pragma once
#include HashTable.h
namespace lyl
{templateclass K, class V, class Hash HashFuncKclass unordered_map{public:struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename HashBucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;typedef typename HashBucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};}}
五、unordered_set封装
#pragma once#include HashTable.hnamespace lyl
{templateclass K, class Hash HashFuncKclass unordered_set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename HashBucket::HashTableK, K, SetKeyOfT, Hash::const_iterator iterator;typedef typename HashBucket::HashTableK, K, SetKeyOfT, Hash::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, K, SetKeyOfT, Hash _ht;};}六、哈希表
#pragma once
#include vector
#includeiostreamnamespace OpenAddress
{enum State{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class Vclass HashTable{public:bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子超过0.7就扩容//if ((double)_n / (double)_tables.size() 0.7)if (_tables.size() 0 || _n * 10 / _tables.size() 7){//size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;//vectorHashData newtables(newsize);遍历旧表重新映射到新表//for (auto data : _tables)//{// if (data._state EXIST)// {// // 重新算在新表的位置// size_t i 1;// size_t index hashi;// while (newtables[index]._state EXIST)// {// index hashi i;// index % newtables.size();// i;// }// newtables[index]._kv data._kv;// newtables[index]._state EXIST;// }//}//_tables.swap(newtables);size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V newht;newht._tables.resize(newsize);// 遍历旧表重新映射到新表for (auto data : _tables){if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hashi kv.first % _tables.size();// 线性探测size_t i 1;size_t index hashi;while (_tables[index]._state EXIST){index hashi i;index % _tables.size();i;}_tables[index]._kv kv;_tables[index]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){if (_tables.size() 0){return 0;}size_t hashi key % _tables.size();// 线性探测size_t i 1;size_t index hashi;while (_tables[index]._state ! EMPTY){if (_tables[index]._state EXIST _tables[index]._kv.first key){return _tables[index];}index hashi i;index % _tables.size();i;// 如果已经查找一圈那么说明全是存在删除if (index hashi){break;}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n 0; // 存储的数据个数//HashData* tables;//size_t _size;//size_t _capacity;};
}templateclass K
struct HashFunc
{size_t operator()(const K key){return key;}
};// 特化
template
struct HashFuncstring
{// BKDRsize_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}
};namespace HashBucket
{templateclass Tstruct HashNode{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr), _data(data){}};// 前置声明templateclass K, class T, class KeyOfT, class Hashclass HashTable;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashstruct __HashIterator{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HashIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef __HashIteratorK, T, T, T*, KeyOfT, Hash Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_next ! nullptr){_node _node-_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}else{hashi;}}// 没有找到不为空的桶if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}};templateclass K, class T, class KeyOfT, class Hashclass HashTable{templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct __HashIterator;typedef HashNodeT Node;public:typedef __HashIteratorK, T, T, T*, KeyOfT, Hash iterator;typedef __HashIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin(){Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}~HashTable(){for (auto cur : _tables){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}iterator Find(const K key){if (_tables.size() 0)return end();KeyOfT kot;Hash hash;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){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){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}// 休息一下15:55继续// size_t newsize GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes 28;static const unsigned long __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};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}pairiterator, bool Insert(const T data){KeyOfT kot;iterator it Find(kot(data));if (it ! end()){return make_pair(it, false);}Hash hash;// 负载因因子1时扩容if (_n _tables.size()){/*size_t newsize _tables.size() 0 ? 10 : _tables.size()*2;HashTableK, V newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newht._tables);*///size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newsize GetNextPrime(_tables.size());vectorNode* newtables(newsize, nullptr);//for (Node* cur : _tables)for (auto cur : _tables){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.swap(newtables);}size_t hashi hash(kot(data)) % _tables.size();// 头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode, this), false);;}size_t MaxBucketSize(){size_t max 0;for (size_t i 0; i _tables.size(); i){auto cur _tables[i];size_t size 0;while (cur){size;cur cur-_next;}//printf([%d]-%d\n, i, size);if (size max){max size;}}return max;}private:vectorNode* _tables; // 指针数组size_t _n 0; // 存储有效数据个数};
}
