酒店网站解决方案,网站系统设计方案,wordpress框架播放器,越秀公司网站建设unordered_map#xff0c;unordered_set模拟实现 哈希表源代码哈希表模板参数的控制仿函数增加正向迭代器实现*运算符重载-运算符重载运算符重载! 和 运算符重载begin()与end()实现 unordered_set实现unordered_map实现map/set 与 unordered_map/unordered_set对比哈希表… unordered_mapunordered_set模拟实现 哈希表源代码哈希表模板参数的控制仿函数增加正向迭代器实现*运算符重载-运算符重载运算符重载! 和 运算符重载begin()与end()实现 unordered_set实现unordered_map实现map/set 与 unordered_map/unordered_set对比哈希表调整后代码 哈希表源代码
templateclass K
struct HashFunc
{size_t operator()(const K key){//所有类型都强转为size_t类型return (size_t)key;}
};//模板特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};
namespace HashBucket
{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;}}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){//如果该键值对存在就返回falseif (Find(kv.first)){return false;}Hash hash;//如果负载因子为1就扩容if (_size _tables.size()){//创建一个新的哈希表vectorNode* newTables;size_t newSizes _size 0 ? 10 : 2 * _tables.size();//将每个元素初始化为空newTables.resize(__stl_next_prime(_tables.size()), nullptr);//将旧表结点插入到新表当中for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){//记录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){//哈希表大小为0删除失败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 (hash(hash(cur-_kv.first)) key){if (prev){prev-_next cur-_next;}else{_tables[hashi] cur-_next;}//删除该结点delete cur;_size--;return true;}prev cur;cur cur-_next;}//删除结点不存在返回falsereturn false;}size_t Size(){return _size;}size_t TableSize(){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;}private:vectorNode* _tables;size_t _size 0;};
}哈希表模板参数的控制
unordered_set属于K模型unordered_map属于KV模型但是在底层上我们都是用一个哈希表来实现的所以我们需要将哈希表的第二个参数设置为T。
templateclass K, class Tstruct HashNode{T _data;HashNodeT* _next;//构造函数HashNode(const T data):_data(data),_next(nullptr){}};templateclass K, class T, class Hash HashFuncKclass HashTable{typedef HashNodeT Node;public://......private:vectorNode* _tables;size_t _size 0;
};T模板参数可能只是键值Key也可能是由Key和Value共同构成的键值对。如果是unordered_set容器那么它传入底层红黑树的模板参数就是Key和Key
templateclass K, class Hash HashFuncK
class unorder_set
{
public://...
private:HashBucket::HashTableK, K, Hash _ht;
};如果是unordered_map容器那么它传入底层红黑树的模板参数就是Key和Value
templateclass K, class V, class Hash HashFuncK
class unorder_map
{
public://...
private:HashBucket::HashTableK, pairK, V, Hash _ht;
};仿函数增加
对于unordered_set容器我们需要进行键值比较就是对key值进行比较也就是直接比较T就可以了但是对于unordered_map容器来说我们需要比较的是键值对keyvalue中的key我们需要先将key提取出来在进行比较。
所以我们需要在上层unordered_set和unordered_map中各提供一个仿函数根据传入的T类型分开进行比较操作
map仿函数
templateclass K, class V, class Hash HashFuncK
class unorder_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public://...
private:HashBucket::HashTableK, pairK, V, Hash, MapKeyOfT _ht;
};set仿函数
templateclass K, class Hash HashFuncK
class unorder_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public://...
private:HashBucket::HashTableK, K, Hash, SetKeyOfT _ht;
};正向迭代器实现
哈希表只存在正向迭代器哈希表的正向迭代器实际上是对整个哈希表进行了封装
//前置声明
templateclass K, class T, class Hash, class KeyOfT
class HashTable;templateclass K, class T, class Hash, class KeyOfT
struct __HashIterator
{typedef HashNodeT Node;typedef HashTable K, T, Hash, KeyOfT HT;typedef __HashIterator K, T, Hash, KeyOfT Self;Node* _node;HT* _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;}}//找完整个哈希表就指向nullptrif (i _pht-_tables.size()){_node nullptr;}}return *this;
}! 和 运算符重载
! 和 就是判断是不是同一个结点
//!
bool operator!(const Self s)
{return _node ! s._node;
}
//
bool operator(const Self s)
{return _node s._node;
}begin()与end()实现
begin函数返回哈希表当中第一个不为nullptr位置的正向迭代器。end函数返回哈希表当中最后一个位置下一个位置的正向迭代器这里直接用空指针构造一个正向迭代器。
class HashTable
{typedef HashNodeT Node;templateclass K, class T, class Hash, class KeyOfTfriend struct __HashIterator;
public:typedef __HashIterator K, T, Hash, KeyOfT iterator;iterator begin(){//从前往后遍历整个数组for (size_t i 0; i _tables.size(); i){//找到不为空的位置并返回该位置迭代器if (_tables[i]){return iterator(_tables[i], this);}}//最后返回end();return end();}iterator end(){//返回一个为空的位置的迭代器return iterator(nullptr, this);}
}unordered_set实现
templateclass K, class Hash HashFuncK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename HashBucket::HashTable K, 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:HashBucket::HashTableK, K, Hash, SetKeyOfT _ht;
};unordered_map实现
templateclass K, class V, class Hash HashFuncK
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:typedef typename HashBucket::HashTable K, pairK, V, Hash, MapKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){_ht.Insert(key);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}
private:HashBucket::HashTableK, pairK, V, Hash, MapKeyOfT _ht;
};map/set 与 unordered_map/unordered_set对比
map/set 底层是使用红黑树实现的unordered_map/unordered_set底层是用哈希表进行实现的两者的底层实现是不同的对于少量的数据他们的增删查改没有区别但是对于大量的数据unordered系列是要更胜一筹的特别是对于查找来说unordered系列基本可以一直保持高效率
哈希表调整后代码
#pragma oncetemplateclass K
struct HashFunc
{size_t operator()(const K key){//所有类型都强转为size_t类型return (size_t)key;}
};//模板特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};namespace HashBucket
{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 HashTable K, T, Hash, KeyOfT HT;typedef __HashIterator K, 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;}}//找完整个哈希表就指向nullptrif (i _pht-_tables.size()){_node nullptr;}}return *this;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){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 __HashIterator K, 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;//如果该键值对存在就返回falseiterator ret Find((kot(data)));if (ret ! end()){return make_pair(ret, false);}//如果负载因子为1就扩容if (_size _tables.size()){//创建一个新的哈希表vectorNode* newTables;size_t newSizes _size 0 ? 10 : 2 * _tables.size();//将每个元素初始化为空newTables.resize(__stl_next_prime(_tables.size()), nullptr);//将旧表结点插入到新表当中for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){//记录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){//哈希表大小为0删除失败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 (hash(kot(cur-_data)) key){if (prev){prev-_next cur-_next;}else{_tables[hashi] cur-_next;}//删除该结点delete cur;_size--;return true;}prev cur;cur cur-_next;}//删除结点不存在返回falsereturn false;}private:vectorNode* _tables;size_t _size 0;};
}
