当前位置：首页 > 行业知识 > C++ 模拟实现unordered

行业知识

C++ 模拟实现unordered

2026-10-20 16:43:52 来源：互联网转载

��录

（）

一、原始哈希表

（）

二、改造哈希表

1、模版特化

2、适配数据类型

3、迭代器

4、哈希表引入迭代器

5、修改find函数

6、修改insert函数

三、set

四、map

完整版代码

哈希表

unordered_map

unordered_set

一、原始哈希表

原始哈希表代码如下：（使用拉链法）

namespace HashBucket1{templatestruct HashNode{HashNode* _next;pair _kv;HashNode(const pair& kv):_next(nullptr),_kv(kv){}};templatestruct HashFunc{size_t operator()(const K& key){return key;}};templatestruct HashFunc{//BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};templateclass HashTable{typedef HashNode Node;private:vector _tables;size_t _n = 0;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if(prev==nullptr)_tables[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}else {prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i = 0;for (; i  prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pair& kv){if (Find(kv.first)){return false;}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i _next;}if (size > max)max = size;}return max;}};}

二、改造哈希表

接下来，我们对哈希表代码进行改造。

1、模版特化

模版的特化我们选择移动到命名空间外部，方便后续调用。

templatestruct HashFunc{size_t operator()(const K& key){return key;}};templatestruct HashFunc{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};namespace HashBucket{、、、、};}

2、适配数据类型

由于unordered_map&set存储的数据类型不同，所以我们将数据类型的选择权交给unordered_map&set本身。

由此新增了template和template，它们都是模板参数声明。它们声明了一个模板参数，第一个参数是一个类型，第二个参数是一个函数对象。

我们需要将节点结构体RBTreeNode中的数据成员_data的类型改为模板参数T。这样，每个节点就可以存储不同类型的数据，以适应map的节点存储pair结构、set的节点存储key。

namespace HashBucket{templatestruct HashNode{HashNode* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};}

模板参数 KeyOfT 在 unordered_map 和 unordered_set 中被用作一个函数对象（仿函数），用于从存储的数据类型中提取键。通过提供一个自定义的函数对象类型，你可以指定如何从数据类型中提取键，以便在哈希表中进行存储和查找。

`KeyOfT`是一个辅助类也叫作仿函数，用于从值中提取键。在`set`中，键和值的类型相同，因此`KeyOfT`可以直接使用template。而在`map`中，键和值的类型不同，因此我们对于相应的仿函数做出针对性设计。

对于`map`类，我们需要将`KeyOfT`修改为适应`pair`类型的辅助类。我们可以定义一个新的辅助类（仿函数）`MapKeyOfT`，其内部使用重载了函数调用运算符 operator()，这个辅助类的作用是从`pair`类型的值中提取出键`K`，即仿函数返回值为 kv.first。同时，我们将`RBTree`的第三个模板参数修改为`MapKeyOfT`。

#pragma once#include "HashTable.h"namespace bit{templateclass unordered_map{public:struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};private:HashBucket::HashTable _ht;};

对于`set`类，我们需要将`KeyOfT`修改为配合map使用的辅助类。我们可以定义一个仿函数`SetKeyOfT`，通过重载operator()直接返回key。同时，我们将第三个模板参数修改为’SetKeyOfT'。

#pragma once#include "HashTable.h"namespace bit{templateclass unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:HashBucket::HashTable _ht;};}

接着修改哈希表中的插入函数，定义KeyOfT kot;，通过kot获取节点元素的键 kot(cur->_data)。

namespace HashBucket{templatestruct HashNode{HashNode* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};templateclass HashTable{typedef HashNode Node;public:bool Insert(const T& data){KeyOfT kot;            if (Find(kv.first))            {            return false;            }Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}private:vector _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};}

3、迭代器

namespace HashBucket{// 前置声明templateclass HashTable;templatestruct __HashIterator{typedef HashNode Node;typedef HashTable HT;typedef __HashIterator Self;typedef __HashIterator Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator& it):_node(it._node), _ht(it._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 != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi _tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}// 没有找到不为空的桶if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};}

前置声明：

template

class HashTable;

前置声明：前置声明是一种声明方式，它允许我们在一个类、函数或者变量的定义实际出现之前就声明它。这在处理循环依赖或者提高编译速度的时候非常有用。例如，在这个代码中，HashTable 类在 __HashIterator 类之前被前置声明了，这样 __HashIterator 类就可以在 HashTable 类的定义出现之前就使用它。

_HashIterator是一个模板结构体，它是一个迭代器，用于遍历哈希表中的元素。它的模板参数包括：
- K：键的类型。
- T：值的类型。
- Ref：引用类型，通常为T&或const T&。
- Ptr：指针类型，通常为T*或const T*。
- KeyOfT：一个函数对象，用于从值中获取键。
- Hash：一个函数对象，用于计算键的哈希值。
  _HashIterator包含以下成员：
  - Node* _node;：这是一个指向当前迭代器所指向的节点的指针。节点的类型为HashNode，其中T是模板参数。
  - const HT* _ht;：这是一个指向哈希表的指针。哈希表的类型为HashTable，其中K、T、KeyOfT和Hash都是模板参数。
  - 在这个设计中，_node 和 _ht 都被设计为指针类型，主要有以下几个原因：
    - 动态内存管理：使用指针可以动态地创建和销毁对象，这对于管理大量数据和实现复杂的数据结构（如链表、树、图等）非常有用。
    - 节省内存：如果 _node 和 _ht 是对象而不是指针，那么每个迭代器对象都会包含完整的 Node 和 HashTable 对象，这可能会消耗大量的内存。而使用指针，迭代器只需要存储对象的地址，这样可以大大节省内存。
    - 灵活性：指针可以被重新赋值，指向其他对象。这在实现一些复杂的操作（如迭代器的移动、复制等）时非常有用。
    - 访问原对象：在迭代器中，我们需要访问原 HashTable 对象和 Node 对象。通过指针，我们可以直接访问和操作原对象，而不是它们的副本。
    _HashIterator还包含以下成员函数：
    - __HashIterator(Node* node, const HT* ht)：这是一个构造函数，用于初始化迭代器。它接受一个节点指针和一个哈希表指针作为参数。
    - __HashIterator(const Iterator& it)：这是一个拷贝构造函数，用于创建一个新的迭代器，它和参数it指向同一个节点。
    - Ref operator*()：这是一个解引用操作符，它返回当前迭代器所指向的节点的数据。返回类型为Ref，即模板参数中的引用类型。
    - Ptr operator->()：这是一个箭头操作符，它返回一个指向当前迭代器所指向的节点的数据的指针。返回类型为Ptr，即模板参数中的指针类型。
    - bool operator!=(const Self& s)：这是一个不等于操作符，它比较两个迭代器是否不相等。如果两个迭代器指向不同的节点，那么它们就不相等。
    - Self& operator++()：这是一个前置递增操作符，它将迭代器移动到下一个节点。如果当前节点的下一个节点为空，那么它将查找下一个非空的桶。
      4、哈希表引入迭代器
```
namespace HashBucket{templateclass HashTable{templatefriend struct __HashIterator;typedef HashNode Node;public:typedef __HashIterator iterator;typedef __HashIterator const_iterator;iterator begin(){Node* cur = nullptr;for (size_t i = 0; i  在HashTable类中，迭代器的实现主要依赖于__HashIterator模板类。这个类接受6个模板参数，分别是K、T、Ref、Ptr、KeyOfT和Hash。
 
```
      - K：键的类型。
      - T：值的类型。
      - Ref：引用类型，通常为T&或const T&。
      - Ptr：指针类型，通常为T*或const T*。
      - KeyOfT：一个函数对象，用于从T类型的对象中提取键。
      - Hash：一个函数对象，用于计算键的哈希值。
        友元：友元是 C++ 中的一个特性，它允许一个类或者函数访问另一个类的私有或者保护成员。
        
        在这个代码中，__HashIterator 类被声明为 HashTable 类的友元，这样 __HashIterator 就可以访问 HashTable 的私有成员 _tables 和 _n。这在实现一些需要访问私有成员的复杂操作时非常有用。例如，迭代器需要访问和操作容器的内部数据结构，所以通常会被声明为容器类的友元。
        __HashIterator类中定义了一些基本的迭代器操作，包括解引用(operator*和operator->)和递增(operator++)。这些操作使得__HashIterator可以像普通的指针一样使用。
        
        在HashTable类中，begin()和end()函数返回的是iterator类型的对象，这个类型实际上就是__HashIterator。这两个函数分别返回指向哈希表中第一个元素和最后一个元素之后位置的迭代器。
        
        HashTable类还提供了const_iterator类型，这个类型实际上就是__HashIterator。const_iterator和iterator的区别在于，通过const_iterator不能修改它所指向的元素。
        
        5、修改find函数
        
        HashTable类的Find函数返回一个iterator，表示找到的元素的位置。如果没有找到元素，就返回end()。
        
        iterator Find(const K& key){if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}
        
        6、修改insert函数
        
        HashTable类的Insert函数返回一个pair，其中第一个元素是一个iterator，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。
        
        pair Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;}
        
        三、set
        
        #pragma once#include "HashTable.h"namespace bit{templateclass unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashBucket::HashTable::const_iterator iterator;typedef typename HashBucket::HashTable::const_iterator 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& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable _ht;};}
        
        unordered_set类的私有成员变量_ht是一个HashTable类型的对象，它是unordered_set的底层实现。
        
        在这段代码中，unordered_set是一个模板类，它接受两个模板参数：
        
        K：元素的类型。
        Hash：一个函数对象，用于计算元素的哈希值。默认值是HashFunc。
        unordered_set类中定义了一个内部的函数对象SetKeyOfT，它的作用是从元素中提取键。因为在unordered_set中，元素就是键，所以SetKeyOfT直接返回元素本身。
        
        unordered_set类中还定义了两种迭代器类型：iterator和const_iterator。这两种迭代器都是HashTable::const_iterator类型的别名，表示指向元素的常量迭代器。
        
        unordered_set类提供了一些基本的集合操作，包括：
        
        begin()和end()：返回指向集合中第一个元素和最后一个元素之后位置的迭代器。
        insert(const K& key)：插入一个元素，并返回一个pair，其中第一个元素是一个迭代器，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。
        find(const K& key)：查找一个元素，并返回一个迭代器，表示找到的元素的位置。如果没有找到元素，就返回end()。
        erase(const K& key)：删除一个元素，并返回一个bool，表示是否删除成功。
        class unordered_set{ public:typedef typename HashBucket::HashTable::const_iterator iterator;typedef typename HashBucket::HashTable::const_iterator const_iterator;iterator begin(){return _ht.begin();}}
        
        在这个代码中，`HashTable`的`begin()`函数返回的是一个非const迭代器，但在`unordered_set`中，`begin()`函数返回的是一个const迭代器。这是因为在`unordered_set`中，元素的值是不可变的，所以需要返回一个const迭代器来保证元素的值不会被修改。
        
        这里的隐式类型转换是通过`__HashIterator`的构造函数实现的。`__HashIterator`有一个构造函数，它接受一个非const迭代器并将其转换为const迭代器：
        
        struct __HashIterator{ typedef __HashIterator Self; typedef __HashIterator Iterator; __HashIterator(const Iterator& it) :_node(it._node) , _ht(it._ht) {}}
        
        当`_ht.begin()`返回一个非const迭代器时，这个迭代器会被传递给`__HashIterator`的这个构造函数，然后构造函数会返回一个新的const迭代器。这就是`_ht.begin()`如何进行隐式类型转换为const迭代器的。
        
        四、map
        
        #pragma once#include "HashTable.h"namespace testH{templateclass unordered_map{public:struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename HashBucket::HashTable::iterator iterator;typedef typename HashBucket::HashTable::const_iterator 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 pair& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable _ht;};}
        
        在这段代码中，unordered_map是一个模板类，它接受三个模板参数：
        
        K：键的类型。
        V：值的类型。
        Hash：一个函数对象，用于计算键的哈希值。默认值是HashFunc。
        unordered_map类中定义了一个内部的函数对象MapKeyOfT，它的作用是从键值对中提取键。
        
        unordered_map类中还定义了两种迭代器类型：iterator和const_iterator。这两种迭代器都是HashTable的迭代器类型的别名。
        
        unordered_map类提供了一些基本的映射操作，包括：
        
        begin()和end()：返回指向映射中第一个元素和最后一个元素之后位置的迭代器。
        insert(const pair& kv)：插入一个键值对，并返回一个pair，其中第一个元素是一个迭代器，表示插入的元素的位置，第二个元素是一个bool，表示是否插入成功。
        operator[](const K& key)：返回与给定键关联的值。如果映射中不存在这个键，就插入一个与这个键关联的默认值。
        find(const K& key)：查找一个键，并返回一个迭代器，表示找到的元素的位置。如果没有找到元素，就返回end()。
        erase(const K& key)：删除一个键值对，并返回一个bool，表示是否删除成功。
        unordered_map类的私有成员变量_ht是一个HashTable类型的对象，它是unordered_map的底层实现。
        
        完整版代码
        
        哈希表
        
        templatestruct HashFunc{size_t operator()(const K& key){return key;}};// 特化templatestruct HashFunc{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};namespace HashBucket{templatestruct HashNode{HashNode* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};// 前置声明templateclass HashTable;templatestruct __HashIterator{typedef HashNode Node;typedef HashTable HT;typedef __HashIterator Self;typedef __HashIterator Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator& it):_node(it._node), _ht(it._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 != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi _tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}// 没有找到不为空的桶if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};templateclass HashTable{templatefriend struct __HashIterator;typedef HashNode Node;public:typedef __HashIterator iterator;typedef __HashIterator const_iterator;iterator begin(){Node* cur = nullptr;for (size_t i = 0; i _next;delete cur;cur = next;}cur = nullptr;}}iterator Find(const K& key){if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hash;KeyOfT kot;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i = 0;for (; i prime)return __stl_prime_list[i];}return __stl_prime_list[i];}pair Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i _next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};}
        
        unordered_map
        
        #pragma once#include "HashTable.h"namespace testH{templateclass unordered_map{public:struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename HashBucket::HashTable::iterator iterator;typedef typename HashBucket::HashTable::const_iterator 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 pair& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable _ht;};void test_unordered_map1(){unordered_map m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_map::iterator it = m.begin();while (it != m.end()){//it->first = 1;//it->second = 1;cout first