C++中STL容器之哈希容器_1加加stl中哪些容器的底层是哈希表实现的

1. 介绍

前面介绍的 map/multimap、set/multiset底层都是基于红黑树实现的，复杂度大致在$O(logn)$，本次介绍的容器底层都是基于哈希(hash)表，具有很快的映射速度。
基于哈希表，数据的插入和查找的时间复杂度都很低，几乎是常数时间，而代价是需要消耗比较多的内存，因为底层实现一般是用一个下标范围比较大的数组来存储元素，形成很多的桶，然后利用hash函数对键值key进行映射，映射到不同的桶中进行存储。

• 插入操作：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 存放key和value在桶内;
• 取值过程：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 比较桶内元素与key是否相等 -> 取出相等纪录的value;
• hash函数通常会返回一个整数，对应于hash表的数组下标，而数组类型通常为指针指向一片内存或者一个链表头，相同hash映射值的元素都放在这片内存区域，就像一个桶一样。
• 当每个桶内只有一个元素时，查找时只进行一次比较，当很多桶都没有值时，查询更快。当桶内有很多值时，称为冲突；
• 用户可以指定自己的hash函数与比较函数，当采用合适的哈希函数时，能大大减少冲突的情况，减少查找时间；

2.常见容器

常见的基于哈希表的容器有unorder_map/multimap、unorder_set/multiset，其复杂度如下：

上述四种容器采用哈希表实现，不同操作的时间复杂度为：
插入:O(1)，最坏情况O(N)。
查看:O(1)，最坏情况O(N)。
删除:O(1)，最坏情况O(N)。
1
2
3
4

3.unorder_map()

3.1 构造函数

// 模板类型
template <
	class key, // 键的类型
	class T,   // 值的类型
	class Hash = hash<key>, // hash函数，STL提供了不同类型的hash函数实现，也可以自己实现
	class Pred = equal_to<key>, // 判断两个键key是否相等，可以自己实现,接收两个参数，返回bool值
	class Alloc = allocator< pair<const Key,T> > // 内存构造器
	> class unorder_map;
1
2
3
4
5
6
7
8

迭代unorder_map()元素会返回一个键值对，因此定义了一个 value_type类型的返回值类，第一个值为键，第二个值为对应的值

typedef pair<const key,T> value_type;
1

返回的是对于键值对的引用，即指针，所以需要解引用

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 
// or
it->first;
it->second;
1
2
3
4
5
6
7

3.2 成员函数

1.非变动性操作

2.迭代操作

3.元素存取操作

4.搜寻操作

5.修改操作

emplace()

template <class... Args>
pair<iterator, bool> emplace ( Args&&... args );  
1
2

如果key元素是唯一的，在unordered_map中插入新元素，使用Args作为元素构造函数的参数来构造这个新元素。参数为右值引用。
示例：

mymap.emplace ("NCC-1701", "J.T. Kirk");
1

即可插入相应的map元素

insert()

pair<iterator,bool> insert ( const value_type& val );  
1

直接插入元素类型，返回pair类型，返回值pair第一元素是插入元素迭代器，第二元素表示操作是否成功

erase()

iterator erase ( const_iterator position );
size_type erase ( const key_type& k );
iterator erase ( const_iterator first, const_iterator last );  
1
2
3

根据不同的索引擦除插槽中的元素.
clear()

void clear() noexcept;
1

删除容器内所有元素。
swap()

void swap ( unordered_map& ump )  
1

交换两个容器的内容，两个容器的类型必须一致，但大小可以不同。

更多成员函数可到官网查看

4. unorder_set()

unorder_set()也是使用hash表实现，一般适用于以下情况：

• 需要保留一组不同的元素，且不需要排序；
• 需要对单个元素进行访问，且没有遍历。

其函数名称大多数与unorder_map()类似，参考官网