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

C++哈希表：unordered_map与unordered_set全解析

ops 2025/8/24 17:25:03

1. unordered系列关联式容器

1.1 unordered_map

1.2 unordered_map的接口说明

1. unordered_map的构造

2. unordered_map的容量

3. unordered_map的迭代器

4. unordered_map的元素访问

5. unordered_map的查询

6. unordered_map的修改操作

1.3 unordered_set

2. 底层结构

2.1 哈希概念

2.2 哈希冲突

2.3 哈希函数

2.4 哈希冲突解决

2.4.1 闭散列

线性探测哈希表模拟实现：

2.4.2 开散列

2.4.3开散列增容

2.4.4开散列与闭散列比较

开散列哈希表的模拟实现：

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2 N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。

1.1 unordered_map

1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。

6. 它的迭代器包括是前向和反向迭代器。

1.2 unordered_map的接口说明

1. unordered_map的构造

2. unordered_map的容量

3. unordered_map的迭代器

哈希表的正向迭代器（iterator）用于遍历容器中的元素，但与有序容器不同，哈希表的迭代器不支持随机访问，只能逐个遍历，并且是无序的；

4. unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

5. unordered_map的查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

6. unordered_map的修改操作

注意：erase接口可以通过键值或迭代器来删除键值对；

unordered_map作为无序容器，其内部基于哈希表存储，因此在循环中直接调用erase()会导致当前迭代器失效，后续元素无法正常访问，为了避免这个问题，可以使用erase()的返回值更新迭代器。erase()方法会返回指向下一个有效元素的迭代器，可以利用这一点安全地删除元素；或者使用键值删除、迭代器范围删除；

1.3 unordered_set

使用接口与unordered_map类似，但存储的是单一类型的key值，因此不能用[key]访问value；

2. 底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O($log_2 N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

2.2 哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢？

2.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

a.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

b.哈希函数计算出来的地址能均匀分布在整个空间中

c.哈希函数应该比较简单

常见哈希函数:

1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况面试题：字符串中第一个只出现一次字符

2. 除留余数法--(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p将关键码转换成哈希地址

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1. 线性探测

比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入时：

通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素；

删除时

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响（因为4删除了5还在，可能直接认为44存在）。因此线性探测采用标记的伪删除法来删除一个元素。

思考：哈希表什么情况下进行扩容？如何扩容？

关于扩容思路会在后面的模拟实现中介绍。

线性探测哈希表模拟实现：

（1）哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法：

template<class T>
struct HashiValue//生成哈希值的方法
{size_t operator()( const T& x){return x;}
};
template<>
struct HashiValue<string>
{size_t operator()(const string& s){size_t hashi = 0;for (auto e : s){e *= 31;hashi += e;}return hashi;}
};

这是我们内部实现的计算键值的哈希值的方法，只对内置类型和string有效；

（2）哈希表的底层我们采用vector来实现，每一个元素除了存储数据以外，还要有标志状态；

因此将数据和标志状态封装成节点来作为元素即可。代码：

enum State
{Exist,Delete,Empty
};
template<class K,class V>
struct HashiNode
{pair< K, V> _data;State _state;HashiNode(State state= Empty):_state(state){}};

关于构造函数：只需要写一个默认构造，确保将节点初始状态设为空即可，这样，哈希表在进行扩容的时候，会自动调用每个元素节点的默认构造设为空状态！

（3）定义哈希表结构：

template<class K, class V,class Hashi = HashiValue<K>>
class HashiTable
{
public:using Node = HashiNode<K, V>;HashiTable():_n(0){_table.resize(10);}size_t HashiFunc(const size_t& hashi_value){return hashi_value % _table.size();}Node* find(const K& key){}bool insert(pair< K, V> data){}bool erase(const K& key){}private:vector<Node> _table;int _n;//当前哈希表中存储的元素个数
};

先看模版参数：因为我们现在就是采用的KV模型，所以K和V参数就是pair里面的两个类型，而Hashi是一个仿函数对象类型，作用是计算哈希值，默认给的是我们内部实现的HashiValue方法，但该方法只对内置类型和string有效，如果是自定义数据，需要外部传入一个仿函数对象类型，确保能计算出自定义类型的哈希值！

由构造函数可以看出，我们的哈希表在刚创建之初就会给出一些空间，这里我们是把vector的有效字符个数当做哈希表容量，起初每个元素都是标记为空的。

另外我们实现了HashiFunc哈希方法，即除数取余法，将哈希值除以存储容量，取余数即可；

接下来就要实现增删查接口：

（4）find根据键值查找数据

Node* find(const K& key)
{Hashi hashi;//先根据哈希值 % 空间大小，计算出key值应该在的地址size_t id = HashiFunc(hashi(key));while (_table[id]._state != Empty){if (_table[id]._state == Exist && _table[id]._data.first == key){return &_table[id];}id++;id %= _table.size();}return nullptr;
}

思路：首先我们根据键值key和哈希方法计算出该键值对应该在的地址，由于开放定址法的特性，当前地址由于哈希冲突导致该位置已经被占用，所以还要向后去循环式地寻找，如果遇到空位置了，说明根本就没有该键值对！

（5）insert插入键值对

bool insert(pair< K, V> data)
{if (find(data.first)) return false;if (_n * 10 / _table.size() >= 7){HashiTable<K, V, Hashi>newtable;newtable._table.resize(2 * _table.size());for (int i = 0; i < _table.size(); i++){if (_table[i]._state == Exist){newtable.insert(_table[i]._data);}}_table.swap(newtable._table);}Hashi hashi;size_t id = HashiFunc(hashi(data.first));while (_table[id]._state ==Exist){id++;id %= _table.size();}_table[id]._data = data;_table[id]._state = Exist;_n++;return true;
}

思路：

1.哈希表的元素必须是唯一的，所以如果数据已经存在，则插入失败！

2.检查是否扩容：上面说过，负载因子（存储的元素个数/总空间大小）如果大于等于0,7就该扩容了。要扩容，我们可以直接采用vector的resize实现，但并不是对本对象的哈希表直接进行扩容，而是另外创建一个局部哈希表，开辟出当前空间的两倍，然后将本哈希表中的数据全部重新插入局部哈希表中，然后再将两个顺序表的内容交换就好了！

为什么要单独开创一个哈希表重新插入数据？因为我们的顺序表此时需要扩容就说明剩余空间不多了，肯定有很多哈希冲突导致很多数据占用了不属于自己的空间，而扩容后有了更大的空间，理应能够将这些数据重新按照哈希方法分配到自己的地址去，这样可以减少不正确的空间占用，减少哈希冲突！

检查完扩容后，计算出该键值对的地址，如果该地址上没有数据，就直接插入，如果不是空的，就循环式的往后找一个标记为empty或delete的位置插入，注意一定会有一个能插入的位置，因为我们会在还有一部分空间的情况下就扩容！

（6）erase删除键值对

bool erase(const K& x)
{Node* ret = find(x);if (ret){ret->_state = DELETE;_n--;return true;}return false;
}

通过find函数查找到键值对所在的节点地址，然后将状态修改为Delete即可；

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

2.4.2 开散列

1. 开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

图解：

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

简单来讲，开散列的做法就是：一个线性结构中，存储着一个个的单链表头结点，根据键值的哈希值和哈希方法（取余法），计算出该键值对应该在的地址（哪一个头结点），然后就将该键值对放入这个链表中，即使遇到哈希冲突，也都放入这个链表即可！这样就不会像闭散列那样占用其他空间了，大大减少了哈希冲突的概念！

2.4.3开散列增容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

2.4.4开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于闭地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a ，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

开散列哈希表的模拟实现：

与闭散列的哈希表实现的很多地方类似，这里只提供不一样的：

（1）节点定义：

由于开散列的每个元素都是一个单链表的头结点，所以我们要封装出一个链表的节点类型：

template<class K, class V>
struct HashiNode
{pair< K, V> _data;HashiNode<K, V>* _next;HashiNode(pair<K, V> data):_data(data),_next(nullptr){}
};

（2）哈希表的基本框架

template<class K, class V, class Hashi = HashiValue<K>>
class HashiTable
{
public:using Node = HashiNode<K, V>;HashiTable():_n(0){_table.resize(10,nullptr);}~HashiTable(){for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = cur->_next;}_table[i] = nullptr;}}size_t HashiFunc(const size_t& hashi_value){return hashi_value % _table.size();}Node* find(const K& key){}bool insert(pair< K, V> data){}bool erase(const K& key){}private:vector<Node*> _table;int _n;//当前哈希表中存储的元素个数
};

模版参数和哈希方法没有改变，但是构造函数在扩容的时候要给nullptr；

此外还多了一个析构函数，因为顺序表中每个元素都是申请的堆资源，要手动释放；

（3）find

Node* find(const K& key)
{Hashi hashi;int id = HashiFunc(hashi(key));Node* cur = _table[id];while (cur){if (cur->_data.first == key){return cur;}cur = cur->_next;}return nullptr;
}

计算出哈希地址后，遍历单链表即可；

（4）insert

bool insert(pair< K, V> data)
{if (find(data.first))return false;Hashi hashi;if (_n == _table.size()){vector<Node*> newHashi;newHashi.resize(2 * _table.size(),nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){int id = HashiFunc(hashi(data.first));Node* next = cur->_next;cur->_next = newHashi[id];newHashi[id] = cur;cur = next;}cur = nullptr;}_table.swap(newHashi);}int id = HashiFunc(hashi(data.first));Node* cur = _table[id];Node* node = new Node(data);node->_next = cur;cur = node;_n++;return true;
}

思路与闭散列类似，插入之前要先检查扩容，如果要扩容，说明此时的顺序表可能刚好一个位置一个节点，也可能还剩个别的空着，那么扩容后空间大了那么多，我们应该将多挂的那些节点重新分配出去，让它们挂到自己应该在的位置；

我们的做法是，创建一个vector，然后逐个将本表中的所有节点依次重新按照哈希方法插入到新表里，但是会发现此处的插入逻辑与下面的重复了！实际上，我们可以像闭散列的insert一样，采用创建新哈希表对象，复用insert的做法，复用时一定不会扩容，代码实现上简单，不冗余；

改进代码如下：

bool insert(pair< K, V> data)
{if (find(data.first))return false;Hashi hashi;if (_n == _table.size()){HashiTable<K,V,Hashi> newHashi;newHashi._table.resize(2 * _table.size(), nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){newHashi.insert(cur->_data);}cur = nullptr;}_table.swap(newHashi._table);}int id = HashiFunc(hashi(data.first));Node* cur = _table[id];Node* node = new Node(data);node->_next = cur;cur = node;_n++;return true;
}

再看插入逻辑，其实就是单链表的头插操作！

（5）erase

bool erase(const K& key)
{Hashi hashi;int id = HashiFunc(hashi(data.first));Node* cur = _table[id];Node* parent = nullptr;while (cur){if (cur->_data.first == key){if (parent == nullptr){cur = cur->_next;}else{parent->_next = cur->_next;}_n--;delete cur;return true;}parent = cur;cur = cur->_next;}return false;
}

思路就和单链表的删除节点类似。

查看全文

http://www.xdnf.cn/news/18559.html