网站密码管理制度,wordpress php转html,图标设计在线生成,平顶山建设局网站文章目录 1. 哈希表的改造2. unordered_map3. unordered_set C STL 库中#xff0c;unordered_map 和 unordered_set 容器的底层为哈希表#xff0c;本文将简单模拟哈希表#xff08;哈希桶#xff09;#xff0c;unordered_map 和 unordered_set 只需封装哈希表的接口即可… 文章目录 1. 哈希表的改造2. unordered_map3. unordered_set C STL 库中unordered_map 和 unordered_set 容器的底层为哈希表本文将简单模拟哈希表哈希桶unordered_map 和 unordered_set 只需封装哈希表的接口即可实现。 1. 哈希表的改造 模板参数列表的改造 K关键码类型T不同容器 T 的类型不同如果是 unordered_mapT 代表一个键值对如果是 unordered_setT 为 KKeyOfT从 T 中获取 KeyHash哈希函数仿函数对象类型哈希函数使用除留余数法需要将 Key 转换为整型数字才能取模 templateclass K, class T, class KeyOfT, class Hash
class HashTable;增加迭代器操作 // 为了实现简单在哈希桶的迭代器类中需要用到HashTable本身
templateclass K, class T, class KeyOfT, class Hash
class HashTable;// 注意因为哈希桶在底层是单链表结构所以哈希桶的迭代器不需要--操作
templateclass K, class T, class KeyOfT, class Hash
struct __HTIterator
{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash 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 操作 templateclass K, class T, class KeyOfT, class Hash
class HashTable
{templateclass K, class T, class KeyOfT, class Hashfriend struct __HTIterator;typedef HashNodeT Node;public:typedef __HTIteratorK, T, KeyOfT, Hash 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()){vectorNode* 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:vectorNode* _tables; // 指针数组size_t _n;
};2. unordered_map
unordered_map 中存储的是 pairK, V 的键值对K 为 key 的类型V 为 value 的类型Hash 为哈希函数类型unordered_map 在实现时只需将 HashTable 中的接口重新封装即可
templateclass K, class V, class Hash HashFuncK
class unordered_map
{// 通过T获取key的操作struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const pairK, V kv){return _ht.Insert(kv);}private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;
};3. unordered_set
unordered_set 的实现类似于 unordered_map
templateclass K, class Hash HashFuncK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K key){return _ht.Insert(key);}private:hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht;
};END
