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