【知识讲解】 链式哈希表的实现与unordered_map和unordered_set的封装
目录
前言
Part1. 哈希函数
Part2. 插入操作
Part3. 查找操作
Part4. 删除操作
Part5. unordered_map和unordered_set的封装
Part6. 链式哈希表的封装实现
结语
前言
上篇文章：【知识讲解】 哈希表的介绍与实现-CSDN博客
在上篇文章我们讲述了哈希表的开放寻址法，也谈到了他的一些缺点，今天我们来讲一讲链式哈希表的实现，他相比较于开放寻址法有着许多的优势，我们来看看吧。
let's go!!!!!!!!
Part1. 哈希函数
由于除留余数法要用到模运算，其只适用于无符号整形类型（因为负号模后为负数），但是我们在实际运用时，会用到string还有自己设计的一些类型，所以我们需要一个函数让各种类型转化为无符号整型，我们来看代码：
template<class K> struct Hash { size_t operator()(const K& key) { return (size_t)key; } }; template<>//其他无法直接转化为无符号整型的用特化来转化为无符号整型 struct Hash<std::string> { size_t operator()(const std::string& key) { size_t hash0 = 0; for (int i = 0; i < key.size(); i++) { hash0 = hash0 * 131 + key[i];//乘以131来使得分散 } return hash0; } };
Part2. 插入操作
对于链式哈希表我们怎么进行插入呢？我们来看：
我们根据x的key计算出来他在数组中的映射下标，再使用头插这样就做到了O（1）的时间复杂度，关键在于扩容，按道理来说这个是用链表不会超过容量，但是当每个节点下面挂的链表节点更多，在查询时花费时间就会多，所以当负载因子大于一时，我们就要扩容，让数组更多，自然下面挂的链表的节点就会少，增加查询的效率。我们来看扩容：
bool insert(const std::pair<K, V> kv) { if (find(kv.first) != nullptr) { return false; } if (_n >=_tables.size())//扩容 { std::vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));//新的数组 用素数表扩容 for (int i = 0; i < _tables.size(); i++) { Node* tem= _tables[i]; while (tem != nullptr)/ { Node* nextp = tem->_next; size_t hash0 = HashFunc()(tem->_kv.first) % newtable.size();//计算出每一个节点在新数组的映射位置 tem->_next = newtable[hash0];//用头插插入 newtable[hash0] = tem; tem = nextp; } _tables[i] = nullptr; } _tables.swap(newtable);//交换 } size_t hash0 = HashFunc()(kv.first) % _tables.size();//插入 Node* newnode = new Node(kv); newnode->_next = _tables[hash0]; _tables[hash0] = newnode; ++_n; return true; }
Part3. 查找操作
查找就比较简单了，我们来看：
Node* find(const K& key) { size_t hash0 = HashFunc()(key)% _tables.size(); Node* tem = _tables[hash0];//开始在对应的地方查找 while (tem != nullptr) { if (tem->_kv.first == key) { return tem; } tem = tem->_next; } return nullptr; }
Part4. 删除操作
删除的操作就和链表的删除相似，就是删除链表的头节点和中间节点这两个情况，我们来看：
bool erase(const K& key) { size_t hash0 = HashFunc()(key) % _tables.size(); Node* tem = _tables[hash0]; Node* prev = nullptr; while (tem != nullptr) { if (tem->_kv.first == key) { if (prev == nullptr)//分为头节点和中间节点的两个情况 { _tables[hash0] = tem->_next; } else { prev->_next = tem->_next; } delete tem; _n--; return true; } else { prev = tem; tem = tem->_next; } } return false; }
Part5. unordered_map和unordered_set的封装
上面我们完成了链式哈希表的实现，接下来我们就可以使用这个来完成对于unordered_map和unordered_set的封装。我们来看：
这个的封装关键在于迭代器的实现，这迭代器的实现与map和set的迭代器实现相似。我们来都看看吧。我们以unordered_map来举例。
template<class K,class V> class unordered_map { struct MapKeyOfT { const K& operator()(const std::pair<const K,V>& key)//萃取器 萃取出元素方便后续的使用 { return key.first; } }; public: typedef typename HashTable< K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;//封装迭代器 typedef typename HashTable< K, std::pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator end() { return _ht.end(); } iterator begin() { return _ht.begin(); } const_iterator end()const { return _ht.end(); } const_iterator begin()const { return _ht.begin(); } std::pair<iterator, bool> insert(const std::pair<const K,V>& key) { return _ht.insert(key); } iterator find(const K& key) { return _ht.find(key); } bool erase(const K& key) { return _ht.erase(key); } V& operator[](const K& key) { std::pair<iterator, bool> ret = insert({ key,V() });//unordered_map特有的[] 当这个key不存在时 就自动插入 return ret.first->second; } void printf_all_node()const { const_iterator it = begin(); while (it != end()) { std::cout << it->first << " "; ++it; } std::cout << std::endl; } private: HashTable< K, std::pair<const K,V>, MapKeyOfT> _ht;//成员 };
Part6. 链式哈希表的封装实现
我们来看代码：
template<class K> struct Hash { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct Hash<std::string> { size_t operator()(const std::string& key) { size_t hash0 = 0; for (int i = 0; i < key.size(); i++) { hash0 = hash0 * 131 + key[i]; } return hash0; } }; template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; template<class K, class Ref, class Ptr, class T, class KeyOfT, class HashFunc = Hash<K>> class HashIterator; template<class K, class T, class KeyOfT,class HashFunc = Hash<K>> class HashTable { typedef HashNode<T> Node; public: typedef HashIterator<K, T&, T*, T, KeyOfT, HashFunc> iterator; typedef HashIterator<K, const T&, const T*, T, KeyOfT, HashFunc> const_iterator; HashTable() :_tables(__stl_next_prime(0)) , _n(0) { } ~HashTable() { for (int i = 0; i < _tables.size(); i++) { while (_tables[i] != nullptr) { erase(KeyOfT()(_tables[i]->_data)); //析构函数 复用代码 } } } HashTable(const HashTable<K,T, HashFunc>& hash) { for (int i = 0; i < hash._tables.size(); i++) { Node* cur = hash._tables[i]; while (cur != nullptr) { this->insert(cur->_kv);//复用代码 cur = cur->_next; } } } HashTable<K, T, HashFunc>& operator=(HashTable<K, T, HashFunc> hash) { swap(hash); return *this; } iterator end() { return iterator(nullptr, this); } iterator begin() { if (_n == 0) { return end(); } for (int i = 0; i < _tables.size(); i++) { if (_tables[i] != nullptr) { return iterator(_tables[i],this); } } return end(); } const_iterator end()const { return const_iterator(nullptr, this); } const_iterator begin()const { if (_n == 0) { return end(); } for (int i = 0; i < _tables.size(); i++) { if (_tables[i] != nullptr) { return const_iterator(_tables[i], this); } } return end(); } void swap(HashTable<K,T, HashFunc>& hash) { std::swap(_tables, hash._tables); std::swap(_n, hash._n); } std::pair<iterator, bool> insert(const T& kv) { if (find(KeyOfT()(kv)) != end()) { return { find(KeyOfT()(kv)),false }; } if (_n >= _tables.size()) { std::vector<Node*> newtable(__stl_next_prime(_tables.size() + 1)); for (int i = 0; i < _tables.size(); i++) { Node* tem = _tables[i]; while (tem != nullptr) { Node* nextp = tem->_next; size_t hash0 = HashFunc()(KeyOfT()(tem->_data)) % _tables.size(); tem->_next = newtable[hash0]; _tables[hash0] = tem; tem = nextp; } _tables[i] = nullptr;; } _tables.swap(newtable); } size_t hash0 = HashFunc()(KeyOfT()(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) { size_t hash0 = HashFunc()(key) % _tables.size(); Node* tem = _tables[hash0]; while (tem != nullptr) { if (KeyOfT()(tem->_data) == key) { return iterator(tem,this); } tem = tem->_next; } return end(); } bool erase(const K& key) { size_t hash0 = HashFunc()(key) % _tables.size(); Node* tem = _tables[hash0]; Node* prev = nullptr; while (tem != nullptr) { if (KeyOfT()(tem->_data) == key) { if (prev == nullptr) { _tables[hash0] = tem->_next; } else { prev->_next = tem->_next; } delete tem; _n--; return true; } else { prev = tem; tem = tem->_next; } } return false; } size_t size()const { return _tables.size(); } Node* head_node(size_t i)const//由于private修饰我们多加接口来用于迭代器的使用 { return _tables[i]; } private: 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 = std::lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } std::vector<Node*> _tables; size_t _n = 0; }; template<class K,class Ref,class Ptr ,class T, class KeyOfT, class HashFunc> class HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, KeyOfT, HashFunc> HT; typedef HashIterator<K, Ref, Ptr, T, KeyOfT, HashFunc> Self; public: HashIterator(Node* node, const HT* ht)//这里需要加上const上面在const_iterator时 会传过来const修饰的this 如果不加上const 权限缩小报错 因此我们需要加上const 权限平级 :_node(node) ,_ht(ht) { } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& it) { return _node != it._node; } Self& operator++()//++的实现 要是到了一条链的终点 则跳转到下一个下标的链表开头 { Node* old = _node; _node = _node->_next; if (_node == nullptr) { size_t hash0 = HashFunc()(KeyOfT()(old->_data)) % _ht->size(); hash0++; while (hash0 < _ht->size()) { if (_ht->head_node(hash0) != nullptr) { _node = _ht->head_node(hash0); break; } hash0++; } } return *this; } private: Node* _node; const HT* _ht; };
结语
这篇文章我们认识到了unordered_map和unordered_set的封装，接下来，小编还会带来C++11的知识，敬请期待~
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~