网站初期推广,淄博网站制作定制品牌,vps内存wordpress优化,旅游o2o小程序源码目录 一、哈希表核心特性总结
1.开放地址法
2.链地址法
二、unordered_map/unordered_set实现要点分析
1. 哈希表核心实现(HashTable2.h)
(1) 哈希函数处理
(2) 链地址法实现
(3) 迭代器设计
(4) hashtable设计
2. unordered_map实现要点
3. unordered_map实现要点 一…
目录 一、哈希表核心特性总结
1.开放地址法
2.链地址法
二、unordered_map/unordered_set实现要点分析
1. 哈希表核心实现(HashTable2.h)
(1) 哈希函数处理
(2) 链地址法实现
(3) 迭代器设计
(4) hashtable设计
2. unordered_map实现要点
3. unordered_map实现要点 一、哈希表核心特性总结
哈希表有两种表 一种是闭散列开放地址法一种是开散列链地址法我将用画图来带大家理解这两种方法的思路 1.开放地址法
线性探测 v 2.链地址法 二、unordered_map/unordered_set实现要点分析
1. 哈希表核心实现(HashTable2.h)
(1) 哈希函数处理
仅使用首字符会导致大量冲突如所有以相同字母开头的字符串使用BKDR哈希通过累乘质数和字符值获得更好分布
// 默认哈希函数直接类型转换
templateclass K
struct DefaultHashFunc {size_t operator()(const K key) {return (size_t)key;}
};// 字符串特化版本
template
struct DefaultHashFuncstring {size_t operator()(const string str) {size_t hash 0;for(auto ch : str) {hash 131;hash ch;}return hash;}
};(2) 链地址法实现
templateclass T
struct HashNode
{T _data;HashNodeT* next;HashNode(const T data):_data(data), next(nullptr){}
};
(3) 迭代器设计
//前置申明告诉Iterator,申明了哈希表
templateclass K, class T, class KeyOfT, class HashFunc
class HashTable;templateclass K, class T,class Ptr,class Ref, class KeyOfT, class HashFunc
struct HTIterator
{typedef HashNodeT Node; typedef HTIteratorK, T,Ptr,Ref, KeyOfT, HashFunc Self;//这是什么鬼typedef HTIteratorK, T, T*, T, KeyOfT, HashFunc Iterator;Node* _node;//就是不能改*phtconst HashTableK, T, KeyOfT, HashFunc* _pht;//为什么需要节点的指针和哈希的指针/*HTIterator(Node * node,HashTableK, T, KeyOfT, HashFunc* pht):_node(node),_pht(pht){}*///这个_pht加了const的重载HTIterator(Node* node,const HashTableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}//普通迭代器时它是拷贝构造//const迭代器时它是构造HTIterator(const Iterator it):_node(it._node), _pht(it._pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-next){//当前桶还没完_node _node-next;}else{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_table.size();//从下一个位置查找不为空的桶hashi;while (hashi _pht-_table.size()){if (_pht-_table[hashi]){//不为空就退出_node _pht-_table[hashi];return (*this);}else{//为空继续加 hashi;}}_node nullptr;}return *this;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};
(4) hashtable设计 templateclass K, class T,class KeyOfT, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeT Node;////友元声明类模版需要把模版参数带上templateclass K, class T,class Ptr,class Ref ,class KeyOfT, class HashFunc friend struct HTIterator; public:typedef HTIteratorK, T,T*,T, KeyOfT, HashFunc iterator;typedef HTIteratorK, T,const T*,const T, KeyOfT, HashFunc const_iterator;iterator begin(){//找第一个桶for (size_t i 0 ;i _table.size();i){Node* cur _table[i];if (cur){//这里为什么传this ??? 航哥说这里this是哈希表的指针return iterator(cur, this);}}//没有找到return iterator(nullptr, this);}iterator end(){return iterator(nullptr,this);}const_iterator begin()const{//找第一个桶for (size_t i 0;i _table.size();i){Node* cur _table[i];if (cur){return const_iterator(cur, this);}}//没有找到return const_iterator(nullptr, this);}const_iterator end()const{return const_iterator(nullptr, this);}HashTable(){//先把size开到10,然后把剩余的位置另存为空指针_table.resize(10, nullptr);}~HashTable(){for (size_t i 0;i _table.size();i){Node* cur _table[i];while (cur){Node* next cur-next;delete cur;// free cur;cur next;}//因为cur是野指针如果不置空那么他有可能还会指向原来的节点cur nullptr;}}pairiterator,bool insert(const T data){KeyOfT kot;HashFunc hf;iterator it Find(kot(data));//在这里是证明有相同的内容if (it!end()){return make_pair(it,false);}//负载因子到一就扩容if (_n _table.size()){size_t newSize _table.size() * 2;//创建新表HashTableK,T,KeyOfT,HashFunc newht;//这个需要开新节点而且销毁也麻烦//for (size_t i 0;i _table.size();i)//{// //.......// ht.insert();//}vectorNode* newTable;newTable.resize(newSize, nullptr);//便利旧表顺手牵羊把节点签下来挂到新表for (size_t i 0;i _table.size();i){Node* cur _table[i];while (cur){Node* next cur-next;//头插新表size_t hashi hf(kot(cur-_data)) % newSize;cur-next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kot(data)) % _table.size();//头插,这个没看懂Node* newnode new Node(data);newnode-next _table[hashi];_table[hashi] newnode;_n;return make_pair(iterator(newnode,this), true);}iterator Find(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur,this);}cur cur-next;}return iterator(nullptr,this);}void Print(){for (size_t i 0;i _table.size();i){printf([%d]-, i);Node* cur _table[i];while (cur){cout cur-_kv.first - cur-_kv.second -;cur cur-next;}printf(NULL\n);}}bool Erase(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (kot(cur-_data) key){if (prev nullptr){_table[hashi] cur-next;}else{prev-next cur-next;}delete cur;return true;}prev cur;cur cur-next;}--_n;return false;}private:vectorNode* _table;//指针数组size_t _n 0;};
2. unordered_map实现要点
templateclass K,class V
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};
public:typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;pairiterator,bool insert(const pairK,V kv){return _ht.insert(kv);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}V operator[](const K key){pairiterator,bool ret_ht.insert(make_pair(key,V()));return ret.first-second;}
private://这种const的特殊属性一般是自己设置hash_bucket::HashTableK,pairconst K,V,MapKeyOfT _ht;
};
3. unordered_map实现要点
templateclass K
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK,K,SetKeyOfT::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, SetKeyOfT::const_iterator const_iterator;iterator begin()const
{return _ht.begin();
}iterator end()const
{return _ht.end();
}
pairiterator,bool insert(const K key)
{//这样写是错的因为这里接受的是const_iterator,返回的是iteratorpairhash_bucket::HashTableK, K, SetKeyOfT::iterator, bool ret _ht.insert(key);return make_pair(ret.first, ret.second);
}private:hash_bucket::HashTableK, K,SetKeyOfT _ht;
};
