利⽤哈希表封装unordered_map和unordered_set

目录

1.通用哈希表实现

1.1 初步结构实现

1.2 初步unordered_map，unordered_set代码实现

2.通用哈希表迭代器实现

2.1 哈希表迭代器基本结构实现

2.2 operator++实现

2.3 前置声明及友元

3. map[ ]实现

4.通用哈希表完整代码

4.1 Hash模版参数的缺省值问题

4.2 完整代码

5.unordered_map和unordered_set代码

1.通用哈希表实现

1.1 初步结构实现

要利用哈希表封装unordered_map和unordered_set，发现unordered_map的参数是pair类型，而unordered_set只有key，正常的话可能会要实现两个哈希表分别对着两个结构进行封装，但是这两个哈希表的大部分接口都类似，此时就可以利用模版，根据传进去的参数，编译器进行实例化，这里用的时链地址法结构实现的哈希

templatestruct HashNode{T _data;HashNode* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class V, class KeyOfT,class Hash = HashFunc>class HashTable{public: private: vector _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 };

注意这里的后面两个模版参数所代表的意思，这里不在叙述

Keyoft模版的意思请移步利用红黑树封装实现map,set

Hash模版的意思请移步哈希表模拟实现

1.2 初步unordered_map，unordered_set代码实现

unordered_map

templateclass unordered_map{struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:private:hash_bucket::HashTable<K, pair, MapKeyOfT, Hash> _ht;};

unordered_set

templateclass unordered_set{struct MapKeyOfT{const K& operator()(const K& kv){return kv;}};public:private:hash_bucket::HashTable _ht;};

2.通用哈希表迭代器实现

2.1 哈希表迭代器基本结构实现

templatestruct HTIterator{typedef HashNode Node;typedef HTIterator Self;Node* _node;HTIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};

对于这里后面三个的模版参数不做叙述

Ref,ptr移步list类的常用接口实现及迭代器

Keyoft请移步利用红黑树封装实现map,set

Hash请移步哈希表模拟实现

2.2 operator++实现

begin()返回第⼀个桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空表⽰。

ierator中有⼀个指向结点的指针，如果当前桶下⾯还有结点， 则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶，那如何计算，其实这里传入哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前 桶位置，依次往后找下⼀个不为空的桶即可。

// 前置声明templateclass HashTable;templatestruct HTIterator{typedef HashNode Node;typedef HTIterator Self;typedef HashTable HT;Node* _node;HT* _ht;//为了寻找下一个桶的位置HTIterator(Node* node,const HT* ht):_node(node),_ht(ht){}Self& operator++(){if (_node->_next){// 当前桶还有数据，走到当前桶下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi _tables.size()){_node = _ht->_tables[hashi];if (_node)break;else++hashi;}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}}

2.3 前置声明及友元

对于operator++的实现，发现要使用HashTable，而HashTable的begin的一些函数也需要HTIterator，这两个是相互依赖的，因此要在HTIterator之前加一个前置声明，在HashTable内部要对HTIterator进行友元声明

//前置声明templateclass HashTable;templatestruct HTIterator{typedef HashNode Node;typedef HTIterator Self;typedef HashTable HT;Node* _node;const HT* _ht;//为了寻找下一个桶的位置HTIterator(Node* node,const HT* ht):_node(node),_ht(ht){}}template<class K, class T, class KeyOfT,class Hash = HashFunc >class HashTable{// 友元声明templatefriend struct HTIterator;typedef HashNode Node;public:typedef HTIterator Iterator;typedef HTIterator ConstIterator;private:vector _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};

3. map[ ]实现

这里的map[ ]实现和红黑树封装实现map,set一样，这里不在叙述，直接给代码，如果需要的请移步利用红黑树封装实现map,set

V& operator[](const K& key){pair ret = insert({ key, V() });return ret.first->second;}

4.通用哈希表完整代码

4.1 Hash模版参数的缺省值问题

templateclass HashTable

这里是用哈希表来封装unordered_map和unordered_set,如果在哈希表内给缺省值，外部的unordered_map和unordered_set就要多传入一个参数，如果不传会无法对字符串和一些自定义类型转换为整数，因此，需要把Hash模版参数缺省值给到unordered_map和unordered_set，内部哈希表的Hash模版就不用给缺省值

4.2 完整代码

template struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};// 特化template struct HashFunc {// 字符串转换成整形，可以把字符ascii码相加即可// 但是直接相加的话，类似\"abcd\"和\"bcad\"这样的字符串计算出是相同的// 这⾥可以⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 131;hash += e;}return hash;}};inline unsigned long __stl_next_prime(unsigned long n){static 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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list +__stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}namespace hash_bucket{templatestruct HashNode{T _data;HashNode* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 前置声明templateclass HashTable;templatestruct HTIterator{typedef HashNode Node;typedef HTIterator Self;typedef HashTable HT;Node* _node;const HT* _ht;//为了寻找下一个桶的位置HTIterator(Node* node,const HT* ht):_node(node),_ht(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){// 当前桶还有数据，走到当前桶下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi _tables.size()){_node = _ht->_tables[hashi];if (_node)break;else++hashi;}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K, class T, class KeyOfT,class Hash = HashFunc >class HashTable{// 友元声明templatefriend struct HTIterator;typedef HashNode Node;public:typedef HTIterator Iterator;typedef HTIterator ConstIterator;Iterator End(){return Iterator(nullptr, this);}Iterator Begin(){if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return End();}ConstIterator Begin() const{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}HashTable():_tables(__stl_next_prime(0)), _n(0){}~HashTable(){for (size_t i = 0; i _next;delete cur;cur = next;}_tables[i] = nullptr;}}HashTable(const HashTable& ht){_tables.resize(ht._tables.size());_n = ht._n;for (size_t i = 0; i _data); // 拷贝kv对if (prev == nullptr){_tables[i] = newNode;}else{prev->_next = newNode;}prev = newNode;cur = cur->_next;}}}pair insert(const T& kv){Hash hs;KeyOfT kot;Iterator it = Find(kot(kv));if (it != End())return { it, false };if (_n ==_tables.size() )//扩容{vector newTatble(__stl_next_prime(_tables.size()+1));//直接把旧表的数据头插到新表for (size_t i = 0; i _next;size_t hashi = hs(kot(cur->_data)) % newTatble.size();cur->_next = newTatble[hashi];newTatble[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTatble);//交换}size_t hash0 = hs(kot(kv)) % _tables.size();Node* newnode = new Node(kv);//头插newnode->_next = _tables[hash0];_tables[hash0] = newnode;++_n;return { Iterator(newnode, this), true };}Iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hash = hs(key) % _tables.size();Node* cur = _tables[hash];while (cur){if (kot(cur->_data) == key){return Iterator(cur, this);}cur = cur->_next;}return End();}bool Erase(const K& key){Hash hs;KeyOfT kot;size_t hash = hs(key) % _tables.size();Node* cur = _tables[hash];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hash] = cur->_next;}else{//中间节点prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};

5.unordered_map和unordered_set代码

这里就非常简单了，就是在哈希表上套了一层壳

unordered_map

namespace chuxin{template<class K, class V, class Hash = HashFunc >class unordered_map{struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair, MapKeyOfT, Hash>::ConstIterator 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();}V& operator[](const K& key){pair ret = insert({ key, V() });return ret.first->second;}pair insert(const pair& kv){return _ht.insert(kv);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair, MapKeyOfT, Hash> _ht; };}

unordered_set

namespace chuxin{template<class K, class V, class Hash = HashFunc >class unordered_set{struct MapKeyOfT{const K& operator()(const K& kv){return kv;}};public:typedef typename hash_bucket::HashTable<K, pair, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair, MapKeyOfT, Hash>::ConstIterator 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();}pair insert(const K& kv){return _ht.insert(kv);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable _ht;};}