当前位置：首页 > news >正文

yo！这里是STL::unordered系列简单模拟实现

news 文章来源：https://blog.csdn.net/phangx/article/details/134096444 2025/5/25 17:23:02

前言

我们之前了解过map和set知道，map、set的底层结构是红黑树，插入查询等操作效率相对较高，但是当树中的节点非常多时，查询的效率也是很好，我们希望呢，最好进行较少的查询就能找到元素。因此，在c++11中，stl又提供了unordered_map和unordered_set等相关关联式容器，使用方法与map、set基本一样，重点是底层结构不同。从名字也可以看出，unordered系列容器是不做排序的，想想也是，很多查询情况下也是不需要排序的。所以下面让我们看看它们的神奇之处吧！

闭散列

        闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的下一个空位置，若找不到下一个空位置说明哈希表已经满了，则需要扩容。

        找下一个空位置的方法有两种，一种是线性探测法，即从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止；另一种是二次探测法，就是步长呈平方式的向后探测（或者左右探测），比如：

        对于线性探测法，当插入24时，计算hashi=4遇到14冲突了，则向后找到hashi=5的空位置存放元素24；对于二次探测法，当再次插入34时，计算hashi=4遇到14冲突了，则计算(hashi+1^2)%10=5遇到24再次冲突，计算(hashi+2^2)%10=8遇到68再次冲突，计算(hashi+3^2)%10=3不冲突，存放到下标为3的位置。插入是如此，查询也是如此，先计算哈希值，遇到冲突了根据解决冲突的方法查询下一个位置，直到遇到空位置说明未查询成功。

思想如上，但实现起来彷佛有点麻烦，比如有两个同义词先后被插入，插入第二个同义词之后，删除第一个插入的同义词，之后查询第二个同义词，那是不是直接遇到空返回查询失败呢？很明显不对，第二个同义词是在的，因此我们在实现时引入一个标识元素状态的state，具体实现如下。

框架

我们知道，哈希表的数据结构是顺序表，所以这里使用vector，那里面的元素放什么呢？首先必然要放一个pair结构体来放对应的key和value，除此之外可以看到下方代码实现中还多了一个state属性，这个是为了标识当前下标元素的状态，其中包括，EMPTY表示该下标没有元素，EXIST表示该下标存在元素，DELETE表示该下标的元素已被删除，为什么要标识DELETE呢？

举个例子，根据hash函数找到了对应下标，但是这个下标没有元素，那就一定代表所查找的关键字就不存在了嘛，不一定，有可能当前元素遇到了冲突被放到了其他位置，之后呢当前这个hash值的位置的元素被删除了，那就得标识DELETE，表示当前对应下标位置得元素不存在，但你要根据解决冲突得办法继续向后找，直到找到EMPTY为止。

所以下方的HashData结构体就是哈希表的元素，状态属性用枚举实现；除此之外呢，可以看到HashFunc类模板，这个是解决不同类型关键字如何转化成下标的问题，比如说，一个int类型做关键字，很好理解，将其取模即可，但是遇到string做关键字如何应对呢？那我们就可以通过这个HashFunc类模板实现将string转化成整型的逻辑（比如字符相加或者相乘等等），重点在于要尽可能具有唯一性，如下实现的逻辑得到的整型更加合适（大佬研究所得）。

将想要作为关键字转化成整型的逻辑实现在HashFunc之后，通过类模板参数传进哈希表的类中使用，如下代码中的class Hash=HashFunc()，这里是将此类模板作为了缺省值，之后在insert、find函数中实例化出对象即可使用。

代码：

enum State
{EXIST,DELETE,EMPTY
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class T>
struct HashFunc
{size_t operator()(const T& t){return (size_t)t;}
};
//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t sum = 0;for (auto i : s){sum *= 131;sum += i;}return sum;}
};template<class K, class V, class Hash=HashFunc<K>>
class HashTable
{
public://...
private:vector<HashData<K, V>> _table;size_t _size = 0;   //存储有效数据的个数
};

核心函数

核心函数在这里我们介绍insert插入函数，find查找函数和erase删除函数，其他接口函数都较为简单，不再赘述。

对于insert，首先是去重，即如果表中存在当前key，就直接插入失败，不再插入；其次就是扩容，当达到你想要的载荷因子（表元素/表容量）就选择扩容，这里我们选择使用复用的方法去扩容，即新实例化出一个哈希表对象，遍历旧表元素，复用insert函数将其插入到新表中，之后将旧表和新表的vector调换即可，新表就没用了，函数结束后自动析构掉；最后呢就是关键插入部分代码，通过hash函数映射出对应下标，如果冲突则使用线性探测法（后面介绍二次探测法）向后探测可以插入的位置，即遇到EXIST就继续找，遇到DELETE或EMPTY就插入，注意在向后找的过程中，记得将遍历下标取模，因为遍历到最后还需要回到开头继续找，找到之后设置好state及size即可。二次探测法与线性探测法相似，只不过线性探测法是顺次一个一个向后找，而二次探测法是平方着向后找（比如hashi+0²、hashi+1²、hashi+2²......，也比如hashi+0²、hashi+1²、hashi-1²、hashi+2²、hashi-2²......），实现逻辑很简单，下方代码可参考。

对于find函数，实现逻辑也是很简单，通过hash函数映射出对应下标，遇到EMPTY就查找失败，遇到EXIST或DELETE就向后找，当遇到EXIST时判断是否与被查找key相等，注意查找成功时返回元素地址，失败时返回null。

对于erase函数，相比之下更简单，使用find函数找到对应元素，将其状态改为DELETE及size-1即可，查找失败对应着删除失败。

代码：

	bool insert(const pair<K, V>& kv){//去重if (find(kv.first))return false;//载荷因子大于0.7需要扩容if (_table.size() == 0 || 10 * _size / _table.size() >= 7){size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;HashTable<K,V,Hash> newHT;newHT._table.resize(newsize);for (auto& i : _table){if (i._state == EXIST){newHT.insert(i._kv);}}_table.swap(newHT._table);}Hash hash;size_t Hashi = hash(kv.first) % _table.size();//线性探测while (_table[Hashi]._state == EXIST)   //元素存在就++，遇到删除或空就插入{Hashi++;Hashi %= _table.size();}_table[Hashi]._kv = kv;_table[Hashi]._state = EXIST;_size++;//二次探测//size_t i = 0;//while (_table[Hashi + i * i]._state == EXIST)//{//	 i++;//	 Hashi %= _table.size();//}//_table[Hashi + i * i]._kv = kv;//_table[Hashi + i * i]._state = EXIST;//_size++;return true;}HashData<K, V>* find(const K& key){if (_size == 0 || _table.size() == 0)return nullptr;Hash hash;size_t Hashi = hash(key) % _table.size();while (_table[Hashi]._state != EMPTY){if (_table[Hashi]._state == EXIST && _table[Hashi]._kv.first == key){return &_table[Hashi];}Hashi++;Hashi %= _table.size();}return nullptr;}bool erase(const K& key){HashData<K, V>* ret = find(key);if (!ret)return false;ret->_state = DELETE;--_size;   //注意控制哈希表属性sizereturn true;}

开散列

开散列，又叫做链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过单链表链接起来，各链表的头结点存储在哈希表中，因此每一个桶中放的都是发生哈希冲突的元素，比如有集合{1，34，22，65，77，24，71，69，9，0}，哈希函数是hashi=Hash(key)%capacity，映射关系如下图：

思路如上，很好理解，并且实现起来不是很麻烦，个人认为开散列的性价比比闭散列要高，至少比它节省空间，下面看看具体实现。

框架

首先，哈希桶也是使用vector实现，因为放入的元素是由链表组成，所以vector的元素应当是一个指针变量，这里我们封装一个HBnode结构体，存储key+value组成的pair结构以及指向下一节点的next指针，除了属性之外，还包括节点的构造函数，用来创建节点以及初始化属性，因此，vector中存储的就是HBnode类型的指针。

其次依旧是在哈希表中提到的HashFunc类模板，用以解决不同类型关键字如何转化成下标的问题，介绍如上。

代码：

template<class K, class V>
struct HBnode
{pair<K, V> _kv;HBnode<K, V>* _next;HBnode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}
};template<class T>
struct HashFunc
{size_t operator()(const T& t){return (size_t)t;}
};
//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t sum = 0;for (auto i : s){sum *= 131;sum += i;}return sum;}
};template<class K, class V, class Hash=HashFunc<K>>
class HashBucket
{typedef HBnode<K, V> node;
public://...
private:vector<node*> _buckets;size_t _size = 0;
};

核心函数

对于insert函数，思路与哈希表的insert函数实现大体一样。扩容方面，不同于哈希表中存储了多少值，就会占用多少下标位置，哈希桶存储了多少值，与占用下标位置数没有关系，因为元素可以连接在同一个下标位置上，也就是形成一个桶，所以这里我们设置触发扩容的条件是元素个数达到vector容量；在哈希表中的扩容部分我们是使用了复用的方式，但是对于这种节点链表也适合吗？不太行，因为旧表上的节点可以重复利用，也就将其拆卸下来装到新表上，所以我们初始化一个新表HashBucket，遍历旧表，将旧表的节点拆卸下来再通过hash函数映射到新表上，之后交换旧表与新表的vector即可；插入方面就是创建新的节点，主要难点还是在于将其插入到链表中，但因其是旧知识，这里也不多赘述，实现可参考下方代码。

对于find函数，相比之下比较简单，遍历表中的各个链表，找到对应节点，将其pair结构体的地址返回，找不到则返回null。

对于erase函数，不能像哈希表中的erase实现一样，先调用find函数找到对应关键字再删除，注意这里删除是删除一个链表节点，我们知道删除链表节点必须找到当前节点的前一个节点，因此我们需要像find函数一样去遍历vector中的每一个链表，找到所要删除的节点，同时记录当前节点的前一个节点，下面就是链表节点的删除操作，只要着重注意一下头删和中间删的操作的区别，其他都是基操，代码参考下方。

代码：

bool insert(const pair<K, V>& kv){Hash hash;if (find(kv.first))return false;if (_size == _buckets.size()){size_t newsize = _buckets.size() == 0 ? 10 : _buckets.size() * 2;HashBucket newHB;newHB._buckets.resize(newsize);for (size_t i = 0; i < _buckets.size(); i++){node* cur = _buckets[i];while (cur){node* curnext = cur->_next;size_t newHashi = hash(cur->_kv.first) % newHB._buckets.size();if (newHB._buckets[newHashi]){cur->_next = newHB._buckets[newHashi];newHB._buckets[newHashi] = cur;}else{newHB._buckets[newHashi] = cur;}cur = curnext;}}_buckets.swap(newHB._buckets);}size_t Hashi = hash(kv.first) % _buckets.size();node* Node = new node(kv);if (_buckets[Hashi]){Node->_next = _buckets[Hashi];_buckets[Hashi] = Node;}else{_buckets[Hashi] = Node;}_size++;return true;}pair<K, V>* find(const K& key){if (_size == 0 || _buckets.size() == 0)return nullptr;Hash hash;size_t Hashi = hash(key) % _buckets.size();node* cur = _buckets[Hashi];while (cur){if (cur->_kv.first == key)return &cur->_kv;cur = cur->_next;}return nullptr;}bool erase(const K& key){if (_size == 0 || _buckets.size() == 0)return false;Hash hash;size_t Hashi = hash(key) % _buckets.size();if (!_buckets[Hashi])return false;node* prev = _buckets[Hashi];if (prev->_kv.first == key)   //头删{_buckets[Hashi] = prev->_next;delete prev;_size--;return true;}node* cur = prev->_next;while (cur){if (cur->_kv.first == key)   //中间删{prev->_next = cur->_next;delete cur;_size--;return true;}prev = cur;cur = cur->_next;}return false;}

哈希表（开散列）的修改

迭代器实现

首先考虑其成员变量需要包括节点指针以及指向此哈希表的指针，因为在实现迭代器++时，需要找到下一个元素，如果没有当前哈希表的信息，就无法找到下一个元素，所以需要一个指向哈希表类的指针，也是正因为如此，迭代器的实现需要哈希表，但是哈希表的实现也需要迭代器，造成了一个“你中有我，我中有你”的局面，需要使用前置声明的方法打破，因此在迭代器的实现之前前置声明了哈希表。

对于构造函数，定义时需传入一个节点指针和当前哈希表指针用以初始化；对于解引用，得到节点中的数据；对于->，得到节点数据的地址；对于关系运算符，重点是比较迭代器的节点；对于迭代器++操作（这里仅强调前置++，后置++类似，并且迭代器只有++操作，无--操作，因为哈希表的迭代器是单向迭代器），根据当前迭代器节点的下一节点的存在情况进行讨论，若下一节点存在则直接将下一节点赋值给迭代器，若下一节点不存在，则通过哈希表指针遍历到当前桶的下一个桶，将下一个桶的第一个节点赋值给迭代器，若后面没有桶了，则给迭代器节点赋值空，代码参考下方。

代码：

//前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashBucket;template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{typedef HBnode<T> node;typedef HashBucket<K, T, Hash, KeyOfT> HB;typedef __HashIterator<K, T, Hash, KeyOfT> Self;node* _node;HB* _hb;   //向上找不到HB的声明定义，需要HB前置声明一下//那为什么不把迭代器定义在HB下面，因为HB中也有使用迭代器，是一个“你中有我，我中有你”的关系，需要前置声明打破一下__HashIterator(node* pnode, HB* phb):_node(pnode), _hb(phb){}T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}bool operator==(const Self& iterator) const{return _node == iterator._node;}bool operator!=(const Self& iterator) const{return _node != iterator._node;}Self& operator++(){if (_node->_next){_node = _node->_next;}else{Hash hash;KeyOfT kot;size_t hashi = hash(kot(_node->_data)) % _hb->_buckets.size();hashi++;while (hashi < _hb->_buckets.size() && !_hb->_buckets[hashi]){hashi++;}if (hashi == _hb->_buckets.size()){_node = nullptr;}else{_node = _hb->_buckets[hashi];}}return *this;}
};

细节修改

首先我们先加上对于迭代器最基本的begin()、end()。其中begin()是返回哈希桶中的第一个桶的第一个节点所构造的迭代器，实现逻辑很简单，即从头遍历表，找到第一个桶（很多地方需要用到哈希表类的成员属性_buckets，所以将迭代器类设置成哈希表类的友元，用以访问哈希表类的_buckets），end()是返回空迭代器，值得注意的是，构造迭代器时传入的哈希表指针可以使用this指针。

其次就是加上迭代器后部分核心函数的修改，

①insert函数返回值变成了pair<iterator,bool>；

②find函数返回值变成了iterator；

③加入了哈希表的析构函数，即将所有桶的节点给释放掉，因为自带的析构函数只会析构掉vector，不会释放内部元素指向的节点。

代码：

template<class K, class T, class Hash, class KeyOfT>
class HashBucket
{typedef HBnode<T> node;template<class K, class T, class Hash, class KeyOfT>friend struct __HashIterator;
public:typedef __HashIterator<K, T, Hash, KeyOfT> iterator;iterator begin(){for (size_t i = 0; i < _buckets.size(); i++){if (_buckets[i])return iterator(_buckets[i], this);}return end();}iterator end(){return iterator(nullptr, this);}~HashBucket(){for (size_t i = 0; i < _buckets.size(); i++){node* cur = _buckets[i];while (cur){node* next = cur->_next;delete cur;_size--;cur = next;}_buckets[i] = nullptr;}}pair<iterator,bool> insert(const T& data){Hash hash;KeyOfT kot;iterator ret = find(kot(data));if (ret != end())return make_pair(ret, false);if (_size == _buckets.size()){size_t newsize = _buckets.size() == 0 ? 10 : _buckets.size() * 2;HashBucket newHB;newHB._buckets.resize(newsize);for (size_t i = 0; i < _buckets.size(); i++){node* cur = _buckets[i];while (cur){node* curnext = cur->_next;size_t newHashi = hash(kot(cur->_data)) % newHB._buckets.size();if (newHB._buckets[newHashi]){cur->_next = newHB._buckets[newHashi];newHB._buckets[newHashi] = cur;}else{newHB._buckets[newHashi] = cur;}cur = curnext;}}_buckets.swap(newHB._buckets);}size_t Hashi = hash(kot(data)) % _buckets.size();node* Node = new node(data);if (_buckets[Hashi]){Node->_next = _buckets[Hashi];_buckets[Hashi] = Node;}else{_buckets[Hashi] = Node;}_size++;return make_pair(iterator(Node, this), true);}iterator find(const K& key){if (_size == 0 || _buckets.size() == 0)return end();Hash hash;KeyOfT kot;size_t Hashi = hash(key) % _buckets.size();node* cur = _buckets[Hashi];while (cur){if (kot(cur->_data) == key)return iterator(cur, this);cur = cur->_next;}return end();}bool erase(const K& key){if (_size == 0 || _buckets.size() == 0)return false;Hash hash;size_t Hashi = hash(key) % _buckets.size();if (!_buckets[Hashi])return false;node* prev = _buckets[Hashi];if (kot(prev->_data) == key)   //头删{_buckets[Hashi] = prev->_next;delete prev;_size--;return true;}node* cur = prev->_next;while (cur){if (kot(cur->_data) == key)   //中间删{prev->_next = cur->_next;delete cur;_size--;return true;}prev = cur;cur = cur->_next;}return false;}
private:vector<node*> _buckets;size_t _size = 0;
};

unordered系列封装

这里介绍unordered_map封装，unordered_set封装情况一致，代码参考如下。

首先考虑成员属性包括一个哈希表实例化的一个对象，注意key依旧是key，但value却是一个pair结构体，unordered_set也是一样，key依旧是key，但value确实一个key，这是因为统一成使用kv模型中的v来存储值，而k仅用来索引，为什么要把key单独拿出来作为一个类模板的参数呢，因为一些地方还是需要用到key的（比如[]操作符需要传进一个key类型的一个对象，是需要用到key类型的）；进而也需要一个KeyOfT的仿函数来返回key，unordered_map是传出pair结构体的first，而unordered_set仅是为了保持一致，传出key即可。

其次，对于begin()、end()、insert()是调用了成员属性哈希表的成员函数，无需过多封装；[]操作符功能是传进key返回value，若表中不存在此key，则插入，对应value使用匿名对象进行默认构造，若存在则直接返回对象value，代码参考如下。

代码（unordered_map）：

template<class K, class V, class Hash = HashFunc<K>>
class Unordered_map
{struct mapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};
public:typedef typename HashBucket<K, pair<K, V>, Hash, mapKeyOfT>::iterator iterator;iterator begin(){return _HB.begin();}iterator end(){return _HB.end();}pair<iterator,bool> insert(const pair<K,V>& data){return _HB.insert(data);}V& operator[](const K& key){pair<iterator, bool> ret = _HB.insert(make_pair(key, V()));return ret.first->second;}
private:HashBucket<K, pair<K,V>, Hash, mapKeyOfT> _HB;
};

代码（unordered_set）：

template<class K, class Hash = HashFunc<K>>
class Unordered_set
{struct setKeyOfT{const K& operator()(const K& key){return key;}};
public:typedef typename HashBucket<K, K, Hash, setKeyOfT>::iterator iterator;iterator begin(){return _HB.begin();}iterator end(){return _HB.end();}pair<iterator,bool> insert(const K& data){return _HB.insert(data);}
private:HashBucket<K, K, Hash, setKeyOfT> _HB;
};

后记

unordered系列容器是c++11提出的，完美地弥补了map与set在多元素情况下查询效率慢的缺点，其使用与它们并无太大的差别，但实现难度上个人认为比set和map底层的红黑树实现要容易许多。本篇重点讲解了底层实现，其使用方法也不可小视，在一些笔试题、oj题上都需要对这些容器的熟练使用，同时两手抓才能将知识点学的扎实，好了，unordered系列容器介绍就是这样，拜拜！

前言

相关概念介绍

哈希概念

哈希冲突与哈希函数

闭散列

框架

核心函数

开散列

框架

核心函数

哈希表（开散列）的修改

迭代器实现

细节修改

unordered系列封装

后记

相关文章：