哈希表与STL中的unordered_map(hash_map)、unordered_set(hash_set)

程序员文章站 2022-03-23 13:13:28

...

1.什么是哈希表，为什么要有哈希表？

总的来讲，哈希表是一种查找和存储结合一体的技术。

想一想我们在顺序表（如数组）中查找是怎么查找的，我们遍历数组，将每一个元素都与给定关键字进行比较，直到查找成功或遍历结束，查找时间复杂度为O(n); 但O(n)实在是太慢了，尤其是在海量数据中查找某一个关键字，所以我们提出了改进查找算法，先将顺序表中元素进行排序（排序时间复杂度不计入查找时间复杂度），然后进行二分查找（Binary Search）,二分查找的时间复杂度为O(logn),就是说如果要从100万份数据中找到我们的关键数据，那么最多进行20次比较就可以找到，200万份的话也只需用21次比较即可，相比顺序查找效率提升了很多，但是20次查找在我们需要频繁查找的时候也会显得有点力不从心，我们不可能按下查找键之后等程序跑一会儿，所以能不能进一步降低查找时间复杂度，提升查找速度呢？答案是肯定的，大牛是厉害的。

我们先看看在有序数组a[ N ]的二分查找中查找到关键字后会发生什么，查找到相应关键字后会成功返回数组的下标i，我们的目的就是找到这个i，然后通过顺序存储位置计算方法，Loc(ai) = Loc(a1) + i*c(c为每个数组元素所占的内存大小)；得到最后的内存地址，将目标元素取出来，所以我们发现我们查找过程中的比较的最终目的都是为了找到目标数据的存储位置，那么为什么不直接将关键字与目标数据的存储位置对应起来呢?就像我问你你家在哪，你根本不需要查找，你和你的家是对应的，而这就是哈希表的核心思想，它的时间复杂度几乎是O(1)。

也就是说我们只需要通过某个函数将关键字和其存储位置相对应起来即可：

存储位置 = f(关键字)

我们通过查找关键字不需要比较就可以获得需要记录的存储位置，这是一种新的存储技术----散列存储技术（将记录存储到其关键字对应的f(key)内存位置）

这种对应关系 f称为哈希函数（Hash）,然后以这种散列存储方式将记录存储到一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表（Hash Table）.

整个散列过程其实只需要两步：

1.将记录存储起来，就是构建哈希表

那我们就需要用明确关键字，然后通过 哈希函数 计算其应该存储的位置，将其存储起来

2.通过关键字进行查找，用相同的哈希函数计算关键字的内存地址，看该地址下的内存空间中是否与该关键字相匹配,匹配则查找成功，否则失败

关于具体采用的哈希函数，这里简单提一下，之后具体分析一下如何调用 unordered_map与 unordered_set

哈希函数构造方法有：

1.直接定址法 f(key) = a*key + b (内存地址分布简单均匀，不会产生冲突，即不会有两个不同的关键字有相同的存储地址)

2.平方取中法、数字分析法、除留余数法等等，还有解决冲突的方法开放定址法、链地址法等等

2.unordered_set 与 unordered_map

2.1unordered_set 与 unordered_map简单介绍

unorder_set 于 unordered_map均是基于哈希表实现的，

两者的存储查找过程基本是类似的：

存储：

1.先分配一大块连续内存存储空间

2.明确键key

3.哈希函数f(key)找到其对应的存储位置

4.这里两者会有不同，unordered_set会将 key值保存到该存储空间，而 unordered_map会将 key-value值保存到该存储空间

查找取值：

1.明确待查找的关键字key

2.通过相同的哈希函数计算该关键字对应的存储地址

3.然后比较存储位置处的元素的key值是否与待查找的key值相等（比较函数），相等则查找成功，不等则查找失败

4.查找成功后两者又有区别，unordered_set返回的key值，而unordered_map返回的是key对应的value值

从上面我们发现，我们需要注重关注的是有关存储位置的哈希函数 和有关是否找到的比较函数

而这两者正是我们在实例化 unordered_set 或 unordered_map对象时需要指定的参数

2.1 unordered_map的使用

在unordered_map中键key和 value相关联，但顺序无关紧要，若关注顺序问题，则用map比较合适

unordered_map<Key,T,HashFun,EqualKey>

Key表示存储的键的类型（可以是用户自定义数据类型，但必须提供相应的HashFun和EqualKey）

T表示Key的相关联的值的类型

HashFun为哈希函数，缺省值为 hash<Key>(系统提供的哈希函数，如果你的Key值是下面的一种类型，则可以缺省，但在自定义Key类型时必须自己定义哈希函数，下面会讨论如何定义哈希函数)

系统提供的hash<float>简化源码，目的是为了说明hash是一个函数对象，返回值为size_t类型（size_t类型简介）

	struct hash<float>
	{	 size_t operator()(const float _Keyval) const noexcept
		{	// hash _Keyval to size_t value by pseudorandomizing transform
		return (_Hash_representation(_Keyval == 0.0F ? 0.0F : _Keyval));	// map -0 to 0
		}
	};

struct hash<int>
struct hash<char*>
struct hash<const char*>
struct hash<char> 
struct hash<unsigned char> 
struct hash<signed char>
struct hash<short>
struct hash<unsigned short> 
struct hash<int> 
struct hash<unsigned int>
struct hash<long> 
struct hash<unsigned long>

EqualKey表示一个返回bool类型的函数对象，其实是一个二元谓词，缺省值为 equal_to<Key>

//equal_to源码
template<class _Ty = void>
	struct equal_to
	{	// functor for operator==
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

	constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator== to operands
		return (_Left == _Right);
		}
	};

可以看出它的返回值为bool类型，有两个参数，符合二元谓词的特征

知道unordered_map的实例化所需参数后，为了灵活运用就需要构造自己的哈希函数:

已知哈希函数实际上是一个函数对象，用构造函数对象的方法配合映射函数f(key)构造即可

构造流程需要注意以下几点：

使用struct，然后重载operator().
返回是size_t
参数是你要hash的Key的类型。
函数是const类型的

同时为了灵活运用（主要是为了满足根据实际情况定义的数据类型），也需要构建比较构造函数

已知比较构造函数是一个二元谓词，构造流程注意以下几点：

使用struct，然后重载operator().
返回 bool
两个参数是待比较的键Key
定义自己的相等规则

多说不练假把戏，下面以一个例子进行说明：（在ordered_map中添加已经有的数据类型比较简单，Hash_Fun和Equal_to比较函数都可以缺省，所以不再多说，下面向unordered_map中添加自己定义的数据类型）

简单实例：有一个演讲比赛，参数选手有姓名，年纪，参数ID属性，我们需要将选手的ID和其最后取得的名次对应起来。

1.先构建选手类

//演讲比赛，一个选手对应一个比赛结果
class player
{
public:
    player()//之所以要有空的无参构造函数是因为在填入player进行实例化的时候，系统可能会实例化 
    //player类，调用无参，如果我们不提供无参，可能会出现bug
    {}
	player(int ID,string name,int age)
	{
		this->ID = ID;
		this->age = age;
		this->name = name;
	}
public:
	int ID;
	string name;
	int age;
};

2.填入自定义的数据类型，我们需要为其提供哈希函数对象，找到其应该存储的位置，因为关键词为选手ID，进行ID与存储位置的映射

//两种自己定义的数据类型，需要写出自己的哈希函数和查找时需要用到的比较函数
//哈希函数在这里是一个函数对象，我们想要用ID来进行查找
//为方便，这里选取的哈希函数比较简单 存储位置 = Key
struct IDhash
{
	size_t operator()(const player& p)const
	{
		return size_t(p.ID);
	}
};

3.填入自定义数据类型，我们查找时需要用到比较函数，因为调用的是equal_to<Key>,Key为自定义数据类型，所以需要定义自己的比较函数，比较关键字选手ID是否相等，相等返回true，否则返回false

//比较函数是一个二元谓词
struct equal_ID
{
	bool operator()(const player & p1,const player & p2) const
	{
		return p1.ID == p2.ID;
	}
};

4.准备工作完毕，开始向unordered_map中添加元素

//先实例化选手类
player xiaoming(101, "xiaoming", 23);
player xiaoyi(102, "xiaoyi", 25);
player xiaozheng(103, "xiaozheng", 13);
player xiaoyang(104, "xiaoyang", 23);
player xiaoshu(105, "xiaoshu", 12);
player xiaojia(106, "xiaojia", 14);

//实例化unordered_map
unordered_map<player,int,IDhash, equal_ID> mymap;

//添加元素
mymap[xiaoming] = 1;//表示xiaoming是第一名
mymap[xiaoyi] = 6;
mymap[xiaozheng] = 3;
mymap[xiaoyang] = 5;
mymap[xiaoshu] = 2;
mymap[xiaojia] = 4;

5.开始查找，我们要知道xaioyi是第几名

cout << mymap[xiaoyi] << endl; //输出结果为6，查找成功

2.2unordered_map的类方法

unordered_map的方法与map的方法基本类似，下面主要介绍几个常用的方法：

更多细节请点击链接获取《泛型编程与STL》查看，u7jb

查找

iterator unordered_map::find(const key_type & key)
//在ordered_map中查找key，如果找到则返回找到位置的迭代器，没有找到则返回 unordered_map::end()
//迭代器，通常通过判断返回值是否是unordered_map::end()来判断元素是否找到

删除

size_type unordered_map::erase(const key_type& key)
//删除unordered_map中的关键字为key的元素，返回删除的个数，非0即1，成功返回1，不成功返回0

void unordered_map::erase(iterator f,iterator l)
//删除unordered_map中的迭代器 [f,l)的元素

插入

mapped_type& unordered_map::operator[](const key_type&  key)

pair<iterator,bool> unordered_map::insert(const value_type & x)
//将x插入到unordered_map中，如果x确实被插入了，返回值pair的第二部分为true,否则，如果x没有被插入，则pair的第二部分为false

这里先简单谈一下 mapped_type 和value_type类型，再说两个插入函数的区别与用法

mapped_type指的是与key_type相关联的object型别，在这里指的就是键对应的值T（unordered_map中的T），它是一个元素，我们通常说的值value

value_type是存储在unordered_map中的object型别，即上文中我们提到的找到key对应的存储空间，然后将键key与值value一起放到存储空间中，而键key与value就组成了这种value_type类型,它实际上是以对组pair形式出现的，所以我们用insert形式插入时，需要先将键key与value转换为对组形式，然后插入

比如接着上文，我们再初始化一个选手，名叫 "ergouzi"，它是第7名

player ergouzi(107, "ergouzi", 15);

//插入
mymap.insert(pair<player,int>(ergouzi,7));

将 pair<player,int>(ergouzi,7) 插入到unordered_map中，如果确实被插入了，返回值pair<iterator,bool>的第二部分为true,否则，如果没有被插入，即pair<iterator,bool>已经存在ergouzi的ID，则的第二部分为false

而对于operator[ ],它实际上就是一次重载，一种为了方便而产生的简写，不同之处在于如果我们写如下代码：

player ergouzi(107, "ergouzi", 15);

//插入
mymap[ergouzi] = 8;

即使之前我们已经插入了二狗子，排名第7，但是operator[ ]会将我们的ergouzi改为第8名，而不会因为unordered_map中已经存在了ergouzi而报错。

实际上 mymap[ ] 等价于 mymap.insert(value_type(key,mapped_type())).first->second

解释：insert返回的是pair<iterator,bool>,first表明取出unordered_map中键为key的iterator,

iterator->first指向键key,iterator->second指向键关联的value

判断是否为空已经判断unordered_map中的元素个数

bool unordered_map::empty()
//空返回true,否则返回false

size_type unordered_map::size()
//返回unordered_map中元素的个数

2.3 unordered_set

unorder_set<Key,HashFun,EqualKey>

与unordered_map基本类似

参考文献：《大话数据结构》

《泛型编程与STL》

相关标签：哈希表 unordered_map hash_map unordered_set

上一篇：广东理工学院是一本还是二本大学？是几本？在全国排名多少？

下一篇： 43. Multiply Strings

哈希表与STL中的unordered_map(hash_map)、unordered_set(hash_set)

1.什么是哈希表，为什么要有哈希表？

2.unordered_set 与 unordered_map

2.1unordered_set 与 unordered_map简单介绍

2.1 unordered_map的使用

2.2unordered_map的类方法

2.3 unordered_set

C++ STL中哈希表Map 与 hash_map 介绍

C++ STL中哈希表Map 与 hash_map 介绍

哈希表与STL中的unordered_map(hash_map)、unordered_set(hash_set)