C++哈希表unordered_map的使用以及与map和hash_map的对比

刺骨的言语ヽ痛彻心扉 2022-11-21 11:33 201阅读 0赞

### 哈希表 ###

*  c++中map与unordered\_map的区别
 *   *  内部实现机理
     *  优缺点以及适用处
     *   *  map 优点
         *  map缺点
         *  unordered\_map 优点
         *  unordered\_map 缺点
 *  unordered\_map是hash\_map的替代名称
 *   *  hash\_map原理
 *  unordered\_map详解
 *   *  1. 原型
     *  2. 说明
     *  3. 容器属性
 *  4. 常用函数
 *  unordered\_set 集合形式的哈希表

# c++中map与unordered\_map的区别 #

## 内部实现机理 ##

*  map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
 *  unordered\_map: unordered\_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

## 优缺点以及适用处 ##

### map 优点 ###

**有序性**，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

### map缺点 ###

**空间占用率高**，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间  
**适用处，对于那些有顺序要求的问题，用map会更高效一些**

### unordered\_map 优点 ###

因为内部实现了哈希表，因此其**查找速度快**

### unordered\_map 缺点 ###

哈希表的建立比较耗费时间  
适用处，对于**查找问题**，unordered\_map会更加高效.

# unordered\_map是hash\_map的替代名称 #

最初的 C++ 标准库中没有类似 hash\_map 的实现，但不同实现者自己提供了非标准的 hash\_map。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。从 C++ 11 开始，hash\_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered\_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。

## hash\_map原理 ##

hash\_map基于hash table（哈希表）。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。

hash\_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

1、得到key  
2、通过hash函数得到hash值  
3、得到桶号(一般都为hash值对桶数求模)  
4、存放key和value在桶内。

其取值过程是：  
1、得到key  
2、通过hash函数得到hash值  
3、得到桶号(一般都为hash值对桶数求模)  
4、比较桶的内部元素是否与key相等，若都不相等，则没有找到。  
5、取出相等的记录的value。  
hash\_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).

由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash\_map时需要指定的参数。在没有指定hash函数和比较函数的时候，会有一个缺省的函数。

# unordered\_map详解 #

## 1. 原型 ##

template < class Key,                                    // unordered_map::key_type
          class T,                                      // unordered_map::mapped_type
          class Hash = hash<Key>,                       // unordered_map::hasher
          class Pred = equal_to<Key>,                   // unordered_map::key_equal
          class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
          class unordered_map;

## 2. 说明 ##

*  unordered\_map 是一种无序关联容器，用于存储由键值对，并且允许根据其 Key 值快速检索各个元素。
 *  在 unordered\_map 容器中，Key 值通常用来唯一标识元素，映射值是与该 Key 值关联内容的对象。Key 值与映射值的类型可能不同。
 *  在 unordered\_map 内部，元素没有按照其 Key 值与映射值的任何顺序进行排序 ，而是根据它们的 Hash 值组织成**桶**，允许它们通过其 Key 值直接快速访问单个元素（通常具有常数等级的平均时间复杂度）。
 *  unordered\_map 实现了直接访问操作符 (operator\[\])，它允许使用 Key 值作为输入参数，直接访问映射值。
 *  容器中的迭代器至少是前向迭代器。

## 3. 容器属性 ##

*  关联性，关联容器中的元素的参考地址指的是其 Key 值，而不是他们在容器中的绝对地址；
 *  无序性，无序容器使用 Hash 表来组织元素，这些 Hash 表允许无序容器通过 Key 值快速访问元素；
 *  映射  
    每个元素将一个 Key 值与映射值关联起来，Key 值用于标识其主要内容是映射值的元素；
 *  唯一关键值，容器中不存在同时拥有相同 Key 值的两个元素；
 *  分配器感知，map 容器使用分配器对象动态处理其存储需求。

# 4. 常用函数 #

**(1) bucket**  
原型 size\_type bucket ( const key\_type& k ) const;  
说明  
定位元素所在的桶，返回 Key 值为输入参数 k 的元素的所在桶号。  
桶是容器内部 Hash 表中的一个槽，槽中的元素根据 Key 值分配元素。桶号的编号从 0 到(bucket\_count - 1)。桶中单个元素可以通过 unordered\_map::begin 和 unordered\_map::end 返回的范围迭代器进行访问。

for (auto& x : mymap3) {
        
        std::cout << "Element [" << x.first << ":" << x.second << "]";
        // 返回元素所在桶号
        std::cout << " is in bucket #" << mymap3.bucket(x.first) << std::endl;
    }

**(2) count**  
原型 size\_type count ( const key\_type& k ) const;  
说明  
使用给定的 Key 值计算元素。搜索容器中 Key 值为输入参数 k 的元素，并返回找到元素的数量。由于 unordered\_map 容器不允许存在重复的 Key 值，这说明如果容器中存在具有该 Key 值的元素，则该函数返回 1，否则返回 0。  
**(3) 其他**  
其他操作函数基本和 map 相同：  
clear  
清除 map 中所有元素；  
erase  
删除 map 中指定位置的元素；  
insert  
在 map 指定位置添加 pair 类型的元素；  
find  
获取 map 中元素的迭代器；  
begin, end  
map 的正向迭代器的起始位置与终点位置；

#include <iostream>
    #include <string>
    #include <unordered_map>
    
    // reference: http://www.cplusplus.com/reference/unordered_map/unordered_map/at/
    typedef std::unordered_map<std::string, std::string> stringmap;
    
    // 将 a, b 融合为一个 unordered_map
    stringmap merge(stringmap a, stringmap b) {
        
    	// unordered_map 复制构造函数
    	stringmap temp(a);
    	// 范围插入，将 b 全部插入进 a 中
    	temp.insert(b.begin(), b.end());
    	return temp;
    }
    
    int main()
    {
        
    	//============================
    	//   1. unordered_map 元素计算与基础遍历
    	//============================
    	// 定义第一个 unordered_map
    	std::unordered_map<std::string, int> mymap = {
         {
         "Mars", 3000 }, {
         "Saturn", 60000 }, {
         "Jupiter", 70000 } };
    
    	// 对元素进行计算
    	mymap.at("Mars") = 3396;
    	mymap.at("Saturn") += 272;
    	mymap.at("Jupiter") = mymap.at("Saturn") + 9638;
    
    	// auto：自动判断类型
    	// 基于范围的 for 循环，遍历 mymap
    	for (auto& x : mymap) {
        
    		std::cout << x.first << ": " << x.second << std::endl;
    	}
    	std::cout << "mymap.size() is " << mymap.size() << std::endl ;
    	std::cout << "mymap.bucket_count() is " << mymap.bucket_count() << std::endl << std::endl;
    
    	//============================
    	//   2. iterator, 迭代器遍历
    	//============================
    	// 定义第二个 unordered_map
    	std::unordered_map<std::string, std::string> mymap2 = {
         {
         "Australia", "Canberra" }, {
         "U.S.", "Washington" }, {
         "France", "Paris" } };
    	std::cout << "mymap2 contains:" << std::endl;
    
    	// 遍历 mymap2
    	for (auto it = mymap2.begin(); it != mymap2.end(); ++it)
    		std::cout << " " << it->first << ":" << it->second << std::endl;
    	std::cout << std::endl;
    
    	// mymap2 分配的各桶中的元素
    	std::cout << "mymap2's buckets contain:\n";
    	for (unsigned i = 0; i < mymap2.bucket_count(); ++i) {
        
    		std::cout << "bucket #" << i << " contains:";
    		for (auto local_it = mymap2.begin(i); local_it != mymap2.end(i); ++local_it)
    			std::cout << " " << local_it->first << ":" << local_it->second;
    		std::cout << std::endl;
    	}
    
    	//============================
    	//   3. bucker, 桶操作
    	//============================
    	// 定义第三个 unordered_map
    	std::unordered_map<std::string, std::string> mymap3 = {
        
    			{
         "us", "United States" },
    			{
         "uk", "United Kingdom" },
    			{
         "fr", "France" },
    			{
         "de", "Germany" }
    	};
    
    	// 遍历 mymap3
    	for (auto& x : mymap3) {
        
    		std::cout << "Element [" << x.first << ":" << x.second << "]";
    		// 返回元素所在桶号
    		std::cout << " is in bucket #" << mymap3.bucket(x.first) << std::endl;
    	}
    
    	//============================
    	//   4. count ，判断元素是否在容器中
    	//============================
    	// 定义第四个 unordered_map
    	std::unordered_map<std::string, double> mymap4 = {
        
    			{
         "Burger", 2.99 },
    			{
         "Fries", 1.99 },
    			{
         "Soda", 1.50 } };
    
    	// 遍历 mymap4
    	for (auto& x : {
         "Burger", "Pizza", "Salad", "Soda" })
    	{
        
    		// 判断 x 是否在容器中
    		if (mymap4.count(x) > 0)
    			std::cout << "mymap4 has " << x << std::endl;
    		else
    			std::cout << "mymap4 has no " << x << std::endl;
    	}
    
    	//============================
    	//   5. erase ，删除操作
    	//============================
    	// 定义第五个 unordered_map
    	std::unordered_map<std::string, std::string> mymap5;
    	mymap5["U.S."] = "Washington";
    	mymap5["U.K."] = "London";
    	mymap5["France"] = "Paris";
    	mymap5["Russia"] = "Moscow";
    	mymap5["China"] = "Beijing";
    	mymap5["Germany"] = "Berlin";
    	mymap5["Japan"] = "Tokyo";
    
    	// 通过迭代器删除
    	mymap5.erase(mymap5.begin());
    	// 通过 Key 值删除
    	mymap5.erase("France");
    	// 通过迭代器范围删除
    	mymap5.erase(mymap5.find("China"), mymap5.end());
    
    	// 基于范围的 for 循环，遍历展示删除后的 mymap
    	for (auto& x : mymap5)
    		std::cout << x.first << ": " << x.second << std::endl;
    
    	//============================
    	//   6. find ，搜索操作
    	//============================
    	// 定义第六个 unordered_map
    	std::unordered_map<std::string, double> mymap6 = {
        
    			{
         "mom", 5.4 },
    			{
         "dad", 6.1 },
    			{
         "bro", 5.9 } };
    
    	std::string input;
    	std::cout << "who? ";
    	// 输入 mom, dad, bro 中的一个，否则搜索失败返回 Not Found
    	getline(std::cin, input);
    
    	// 根据输入参数 Key 值进行搜索，返回一个迭代器
    	std::unordered_map<std::string, double>::const_iterator got = mymap6.find(input);
    
    	// find 返回值若为 unordered_map 的尾部，则没有在容器中找到
    	if (got == mymap6.end())
    		std::cout << "not found";
    	else
    		std::cout << got->first << " is " << got->second;
    	std::cout << std::endl;
    
    	//============================
    	//   6. insert ，插入操作
    	//============================
    	// 定义第七、八个 unordered_map
    	std::unordered_map<std::string, double>
    		myrecipe,
    		mypantry = {
         {
         "milk", 2.0 }, {
         "flour", 1.5 } };
    
    	// 定义插入元素，类型为 pair 的对象
    	std::pair<std::string, double> myshopping("baking powder", 0.3);
    
    	// 复制插入
    	myrecipe.insert(myshopping);
    	// 移动插入
    	myrecipe.insert(std::make_pair<std::string, double>("eggs", 6.0));
    	// 范围插入
    	myrecipe.insert(mypantry.begin(), mypantry.end());  // range insertion
    	// 初始化列表插入
    	myrecipe.insert({
         {
         "sugar", 0.8 }, {
         "salt", 0.1 } });    // initializer list insertion
    
    	std::cout << "myrecipe contains:" << std::endl;
    	for (auto& x : myrecipe)
    		std::cout << x.first << ": " << x.second << std::endl;
    
    	std::cout << std::endl;
    
    	//============================
    	//   7. 等于运算符 = 操作
    	//============================
    	// 初始化列表
    	stringmap first = {
         {
         "AAPL", "Apple" }, {
         "MSFT", "Microsoft" } };
    	stringmap second = {
         {
         "GOOG", "Google" }, {
         "ORCL", "Oracle" } };
    	// 移动
    	stringmap third = merge(first, second);
    	// 复制
    	first = third;
    
    	std::cout << "first contains:";
    	for (auto& elem : first) std::cout << " " << elem.first << ":" << elem.second;
    	std::cout << std::endl;
    
    	return 0;
    }

# unordered\_set 集合形式的哈希表 #

使用方式同set。 [unordered\_set][unordered_set]  
链接: [参考链接][Link 1].

[unordered_set]: https://en.cppreference.com/w/cpp/container/unordered_set
[Link 1]: https://blog.csdn.net/ajianyingxiaoqinghan/article/details/78542932