目录前言Part1. 哈希函数Part2. 插入操作Part3. 查找操作Part4. 删除操作Part5. unordered_map和unordered_set的封装Part6. 链式哈希表的封装实现结语前言上篇文章【知识讲解】 哈希表的介绍与实现-CSDN博客在上篇文章我们讲述了哈希表的开放寻址法也谈到了他的一些缺点今天我们来讲一讲链式哈希表的实现他相比较于开放寻址法有着许多的优势我们来看看吧。lets go!!!!!!!!Part1. 哈希函数由于除留余数法要用到模运算其只适用于无符号整形类型因为负号模后为负数但是我们在实际运用时会用到string还有自己设计的一些类型所以我们需要一个函数让各种类型转化为无符号整型我们来看代码templateclass K struct Hash { size_t operator()(const K key) { return (size_t)key; } }; template//其他无法直接转化为无符号整型的用特化来转化为无符号整型 struct Hashstd::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计算出来他在数组中的映射下标再使用头插这样就做到了O1的时间复杂度关键在于扩容按道理来说这个是用链表不会超过容量但是当每个节点下面挂的链表节点更多在查询时花费时间就会多所以当负载因子大于一时我们就要扩容让数组更多自然下面挂的链表的节点就会少增加查询的效率。我们来看扩容bool insert(const std::pairK, V kv) { if (find(kv.first) ! nullptr) { return false; } if (_n _tables.size())//扩容 { std::vectorNode* 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来举例。templateclass K,class V class unordered_map { struct MapKeyOfT { const K operator()(const std::pairconst K,V key)//萃取器 萃取出元素方便后续的使用 { return key.first; } }; public: typedef typename HashTable K, std::pairconst K, V, MapKeyOfT::iterator iterator;//封装迭代器 typedef typename HashTable K, std::pairconst 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::pairiterator, bool insert(const std::pairconst 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::pairiterator, 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::pairconst K,V, MapKeyOfT _ht;//成员 };Part6. 链式哈希表的封装实现我们来看代码templateclass K struct Hash { size_t operator()(const K key) { return (size_t)key; } }; template struct Hashstd::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; } }; templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) , _next(nullptr) { } }; templateclass K, class Ref, class Ptr, class T, class KeyOfT, class HashFunc HashK class HashIterator; templateclass K, class T, class KeyOfT,class HashFunc HashK class HashTable { typedef HashNodeT Node; public: typedef HashIteratorK, T, T*, T, KeyOfT, HashFunc iterator; typedef HashIteratorK, 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 HashTableK,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; } } } HashTableK, T, HashFunc operator(HashTableK, 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(HashTableK,T, HashFunc hash) { std::swap(_tables, hash._tables); std::swap(_n, hash._n); } std::pairiterator, bool insert(const T kv) { if (find(KeyOfT()(kv)) ! end()) { return { find(KeyOfT()(kv)),false }; } if (_n _tables.size()) { std::vectorNode* 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::vectorNode* _tables; size_t _n 0; }; templateclass K,class Ref,class Ptr ,class T, class KeyOfT, class HashFunc class HashIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOfT, HashFunc HT; typedef HashIteratorK, 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的封装接下来小编还会带来C11的知识敬请期待~最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~