文章目录
- 1. 哈希表的改造
- 2. unordered_map
- 3. unordered_set
C++ STL 库中,unordered_map 和 unordered_set 容器的底层为哈希表,本文将简单模拟哈希表(哈希桶),unordered_map 和 unordered_set 只需封装哈希表的接口即可实现。
1. 哈希表的改造
-
模板参数列表的改造
- K:关键码类型
- T:不同容器 T 的类型不同,如果是 unordered_map,T 代表一个键值对,如果是 unordered_set,T 为 K
- KeyOfT:从 T 中获取 Key
- Hash:哈希函数仿函数对象类型,哈希函数使用除留余数法,需要将 Key 转换为整型数字才能取模
template
class HashTable; -
增加迭代器操作
// 为了实现简单,在哈希桶的迭代器类中需要用到HashTable本身 template
class HashTable; // 注意:因为哈希桶在底层是单链表结构,所以哈希桶的迭代器不需要--操作 template struct __HTIterator {typedef HashNode Node; typedef HashTable HT; typedef __HTIterator Self; Node* _node; // 当前迭代器关联的节点 HT* _ht; // 哈希桶 - 主要是为了找下一个空桶时候方便 __HTIterator(Node* node, HT* ht) : _node(node) , _ht(ht) {} T& operator*() {return _node->_data; } Self& operator++() {if (_node->_next) {// 当前桶还是节点 _node = _node->_next; } else {// 当前桶走完了,找下一个桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); // 找下一个桶 hashi++; while (hashi < _ht->_tables.size()) {if (_ht->_tables[hashi]) {_node = _ht->_tables[hashi]; break; } hashi++; } // 后面没有桶了 if (hashi == _ht->_tables.size()) {_node = nullptr; } } return *this; } bool operator!=(const Self& s) {return _node != s._node; } }; -
增加通过 T 获取 key 操作
template
class HashTable {template friend struct __HTIterator; typedef HashNode Node; public: typedef __HTIterator 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() {_tables.resize(10, nullptr); _n = 0; } ~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; } } bool Insert(const T& data) {KeyOfT kot; if (Find(kot(data))) return false; Hash hs; // 负载因子到1就扩容 if (_n == _tables.size()) {vector newTables(_tables.size() * 2, nullptr); for (size_t i = 0; i < _tables.size(); i++) {// 取出旧表中节点,重新计算挂到新表桶中 Node* cur = _tables[i]; while (cur) {Node* next = cur->_next; // 头插到新表 size_t hashi = hs(kot(cur->_data)) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = hs(kot(data)) % _tables.size(); Node* newnode = new Node(data); // 头插 newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } Node* Find(const K& key) {KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) {if (kot(cur->_data) == key) {return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) {KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) {if (kot(cur->_data) == key) {// 删除 if (prev) {prev->_next = cur->_next; } else {_tables[hashi] = cur->_next; } delete cur; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector _tables; // 指针数组 size_t _n; };
2. unordered_map
- unordered_map 中存储的是 pair
的键值对,K 为 key 的类型,V 为 value 的类型,Hash 为哈希函数类型 - unordered_map 在实现时,只需将 HashTable 中的接口重新封装即可
template
>class unordered_map {// 通过T获取key的操作 struct MapKeyOfT {const K& operator()(const pair & kv) {return kv.first; } }; public: typedef typename hash_bucket::HashTable , MapKeyOfT, Hash>::iterator iterator; iterator begin() {return _ht.begin(); } iterator end() {return _ht.end(); } bool insert(const pair & kv) {return _ht.Insert(kv); } private: hash_bucket::HashTable , MapKeyOfT, Hash> _ht; }; 3. unordered_set
- unordered_set 的实现类似于 unordered_map
template
>class unordered_set {struct SetKeyOfT {const K& operator()(const K& key) {return key; } }; public: typedef typename hash_bucket::HashTable ::iterator iterator; iterator begin() {return _ht.begin(); } iterator end() {return _ht.end(); } bool insert(const K& key) {return _ht.Insert(key); } private: hash_bucket::HashTable _ht; };
END
- unordered_set 的实现类似于 unordered_map
-