C++哈希表：unordered系列容器详解

本节目标

1.unordered系列关联式容器

2.底层结构

3.模拟实现

4.哈希的应用

5.海量数据处理面试题

unordered系列关联式容器

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

unordered_map

unordered_map的介绍

无序映射（unordered_map）是一种关联式容器，用于存储由键值（key）和映射值（mapped value）组合而成的元素， 并支持基于键的快速元素检索。

在unordered_map中： - 键值通常用于唯一标识元素 - 映射值是与该键关联的内容对象 - 键和映射值的类型可以不同 其内部实现特点：

1. 元素不会按照键值或映射值的顺序排列

2. 基于哈希值组织到桶（buckets）中

3. 通过键值直接访问元素的平均时间复杂度为O(1)

性能特性：

- 无序映射在通过键访问单个元素时比有序映射（map）更快

- 但在迭代访问元素子集时效率通常较低

接口特性：

- 支持直接访问操作符（operator[]），可通过键值直接访问映射值

- 容器提供的迭代器至少为前向迭代器（forward iterators）

unordered_map的接口使用说明

这些是别名，也就是typedef过的，为了方便后续理解，可以自行把常见和常用的了解一下

构造函数

empty (1)	
explicit unordered_map ( size_type n = /* see below */,                                const hasher& hf = hasher(),                                   const key_equal& eql = key_equal(),                           const allocator_type& alloc = allocator_type() );
explicit unordered_map ( const allocator_type& alloc );
range (2)	
template <class InputIterator>  
unordered_map ( InputIterator first, InputIterator last,   size_type n = /* see below */,const hasher& hf = hasher(),const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
copy (3)	
unordered_map ( const unordered_map& ump );
unordered_map ( const unordered_map& ump, const allocator_type& alloc );
move (4)	
unordered_map ( unordered_map&& ump );
unordered_map ( unordered_map&& ump, const allocator_type& alloc );
initializer list (5)	
unordered_map ( initializer_list<value_type> il, size_type n = /* see below */,   const hasher& hf = hasher(),    const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );

 总结：第一个就是构造一个空的非排序map 

            第四个就是拷贝构造

            第五个是迭代器构造

基本上知道第一个和第四个就行了，其他可以自行了解

capacity函数 

iterator函数

 

元素访问函数

 

只要知道[]就可以了

modifier函数

 

学习insert erase clear swap即可

桶操作（具体可以等学习完hash后在了解）

 

unordered_set 

unordered_set的介绍和使用这里就不多加说明了，就是和set差不多，就是底层结构不一样，我们重点学习底层结构

map/set和unordered_map/unordered_set有什么区别和联系？

1.都可以实现key和key-value的搜索场景，并且功能和使用基本一样

2.map/set的底层是用红黑树实现的，遍历出来是有序的，增删查改的时间复杂度为logN

3.unordered_map和unordered_set的底层是用哈希表实现的，遍历出来的是无序的，增删查改的时间复杂度为O(1)

4.map和set是双向迭代器，unordered_map和unordered_set是单向的（仅支持++）

底层结构

请移步我的数据结构篇章中关于哈希表的讲解（包括海量数据的处理都在那一篇章讲解）