文章目录
一. 关联式容器简介
所谓关联式容器，观念上类似关联式数据库：每笔数据（每个元素）都有一个键值（key）和一个实值（value）。当元素被插到关联式容器中时，容器内部结构便按照其键值大小，以某种特定规则将这个元素放置于适当位置。
关联式容器没有头尾，所以不会有所谓
push_back(),pop_back(),push_front(),pop_front()。
首先，关联式容器结构为一个value，value内部为一个键值对构成，也就是 key：data结构，不过对于set（集合）类型的数据结构来说，它的key就是value本身，对于map（映射表）来说，key只是value中的一小部分。因为这些差异，所以对于关联式容器来说，要有一个从value中取出key的规则，这个将在后续介绍。
PS：从“键值对”这个说法来说，本应是
key:value结构，python中也采用了这个写法，而STL中value表示数字的全部，键值为key:data，源码中也全部是这个写法，因此采用与源码相同的说法。
二.使用哈希表作为底层的容器
（1）哈希表 hashtable
1. 哈希表的原理
哈希表又被称为散列表，这很好地说明了它的一大特征：它是无序的。
前面讨论了基于线性表、树表结构的查找方法，这类查找方法都是以关键字的比较为基础的。
在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系， 其查找时间与表的长度有关，特别是当结点个数很多时，查找时要大量地与无效结点的关键字进行比较，致使查找速度很慢。如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是散列查找法 (HashSearch)的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址， 即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或散列法。
——《数据结构C语言版》严蔚敏
哈希的目的就是建立一个映射，将元素与存储它的位置建立一个映射。
什么是hash函数
hash函数致力于将元素映射为一个数，将其作为其唯一的id，即不同的元素其id不同，这对其查找的准确性非常重要。
比如说将int值直接映射为其自身，这也是一种hash。
什么是哈希碰撞
将元素映射为的值看似已经可以作为数组下标了——但是这需要无限的空间，毕竟hash值是没有上限的，因此鉴于当前哈希表的长度M，需要进一步处理：其下标为hash（元素）%M，但是这样引出了另外一个问题：多个元素会映射到一个位置。
如何解决哈希碰撞
解决哈希碰撞有多种方法，比如链地址法、再哈希法、开放地址法等等。因为篇幅问题，这里只介绍STL中采用的链地址法。
即：每个位置放一个链表，存放映射到一个位置的元素。这样会导致假如哈希表的M太小，链表会很长——接下来会介绍如何解决这个问题。
2. 哈希表与红黑树的区别
相比起可能会产生较坏的结果的二叉搜索树，哈希表对插入元素的顺序没有要求（毕竟它本身就是无序的）
同时相比于红黑树，哈希表在查找的时候效率更高一点，为O(1)，其与RB-tree一样可以实现“稠密化”的操作（一个大数组只有少数值有意义，缩小无意义数据所占的空间，使其“粘稠”），其遍历效率为略大于O(n)（n为元素数量）。
3. 哈希表的基本结构
桶 bucket
对于每个链表，STL将其称之为桶“bucket”，桶本身是哈希表内部定义的一个单链表，并没有用到list。
此外，需要一个列表来存放所有桶的指针，哈希表中使用vector来实现，这将方便于桶的扩容。
用到的仿函数
hashFun：将value映射为一个hash值ExtractKey：与红黑树中的KeyofValue相同，从Value中取出keyEqualKey：判断key是否相等（可以为函数/仿函数）Alloc：空间配置器
属性
- 一个vector<node*>buckets，即一个vector，里面包含所有桶
- next_size：表示哈希表的大小
哈希表的大小
STL中定义了一个列表，其中存储了一系列的质数，后一个基本是上一个的两倍，这是哈希表的大小来源——每次需要扩容，就从中选出一个大于等于2*oldSize（或者其他值）的质数作为buckets的新大小，也是新的M。
为什么是质数：质数可以保证映射的更为均匀，不容易引起哈希冲突
因为列表是有序的，因此查找是使用lower_bound，查找效率很高。
因为列表是有上限的，因此对于获取的值需要进行判断，假如值不变说明到达上限，不应该进行扩容了。
4. 哈希表的构造与内存管理
初始化哈希表
初始化只需要调用buckets的reverse来进行重整空间即可（设定为对应的质数，默认为53）。buckets里面的指针都需要置为NULL（目前没有元素），这也说明bucket是单链表。
表格重整
- 重整规则
上文中提到假如哈希表的bucket（链表）长度过长，会导致查找效率很差的后果，因此哈希表有如下设定：假如元素的数量(next_size)大于buckets的长度，则需要进行重整
负载系数：元素数/表格大小
哈希表使用链地址法会导致有些bucket的负载系数大于1，通过上面的规则可以尽量避免bucket的负载系数接近于1。
- 重整操作
首先，需要创建一个新的vector，其大小为大于等于2*oldSize的质数（见上）（当然，若获取的值等于现在的值，说明到达上限，因此不会进行下列操作了）。
创建新的vector后，就是遍历整个哈希表，从每个bucket中取出元素，放到新的bucket中去。这个时候，其实就是hash(元素)% newM （新的长度）。
创建结束后，将新旧vector进行交换（因为vector中只有指向内存的指针，因此开销很小）。
插入操作
- 插入的基本思路
插入的时候需要判断当前的长度+1时候达到了resize的标准，假如是，需要先进行一次重整（即直接调用resize，将长度作为参数传入）。
- insert_unique（不允许重复）
通过函数找到插入元素对应的bucket，因为插入的元素不允许重复，因此需要先遍历当前bucket，若有相同元素，则不需要插入。
假如没有相同元素，则使用头插法插入该元素。
- insert_equal（允许重复）
因为元素可以相同，因此本应不需要进行判断是否有元素相同，但是在源码中还是对是否有相同的元素进行查找，假如有的话，插入在相同元素的前方——这样的话，所有的相同元素会放在一起。
对于这个特性，我觉得在count的时候很适合进行使用，假如找到对应元素，则遍历即可，若下一个元素不是对应元素了，那说明已经找完了，可以提早结束。
可能是因为负载系数不大，同时对insert的插入有过高的要求（假如后续修改就会有bug），所以count并没有利用这个特性
- 在判断元素是否相同使用的正是上面提到的EqualKey
- 插入后返回值为插入结果（假如找到重复元素不能插入，那就是旧有元素的结果）
计算元素的落脚点（元素到index的映射）
刚刚反复提到找到元素对应的bucket，就是使用了bkt_num函数，其经过重载，可以处理多种情况
- 给出value，n ： 从value中取出key，调用4
- value ： 取出key，调用3
- key： 加上n ，调用4
- key ,n：即hash(key) % n
整体思路如“哈希表的原理”一节所示，为其hash值%Size，这个Size不一定是当前的大小，也可能是扩容过程中的新的大小。
复制与删除
- 复制的话，只需要调整buckets的大小（调整到被复制的buckets大小），然后对所有的元素进行拷贝即可
- 删除：删除buckets中每个bucket内的所有node，而不对buckets操作（即vector大小不变）
5.哈希表的迭代器
因为迭代器需要像deque的迭代器一样，有跳回buckets对应的下一个bucket的能力，因此迭代器不止要包含一个指针指向当前node，还包含了一个this，指向当前的类本身。
- node * cur
- hashtable * ht
因为迭代器的遍历是一个个bucket的每一个元素，因此可能遇到空的bucket，这说明遍历数量不止元素个数。
举个极端情况，插入10000个3，因为hash值相同，resize没有效果，resize后会有12289个bucket，因此总共要遍历 10000+12289 次（有12288个空的bucket）
6. 哈希表的具体使用
- find
首先找到对应的bucket，然后对这个链表进行遍历，越界/找到则返回，若没找到则返回NULL，虽然书中没有列出hashtable的end对应什么，但是通过这个可以很简单地推断出为iterator(NULL,this)
7. hash function
STL中对所有默认类型都定义了对应的hash fuction，格式如下：
namespace std
{
template<>
hash<xx> (xx,xx) {return xxxx;}
}
比如
template <>
struct
hash<long> : public __hash_base<size_t, long>
{
size_t operator()(long __val) const noexcept
{
return static_cast<size_t>(__val);
}
};
template<>
struct hash<string>
: public __hash_base<size_t, string>
{
size_t
operator()(const string& __s) const noexcept
{ return std::_Hash_impl::hash(__s.data(), __s.length()); }
};
8. 哈希表相关的容器的名称变化
在C++11之前，哈希表相关的容器被作为SGI（或者是其他版本的编译器）自带的内容而没有被纳入到C++标准中，在C++11标准后，哈希表被纳入STL，从hashxxx（比如hash_set）改名为 unordered_xxx ，我猜测改名为unordered是因为各家之前已经使用了hash的前缀，避免同名。不过unordered(无序)也很贴合其本质，关联式容器有两个，其中红黑树为有序的，而哈希表为无序的。
（2）unordered_set
同样表示不可重复的集合，insert调用的是哈希表的insert_unique
常用API
- constructor（构造函数）：默认构造一个长度为100的哈希表（这个100会被调整为质数表中更高的质数，即193）
- insert
- 插入值
- 插入范围
- insert_noresize
- 插入的话不会重整buckets，调用的是
insert_unique_noresize - 实际上哈希表的insert就是两部分，
resize和insert_unique_noresize
- 插入的话不会重整buckets，调用的是
- erase
- 删除对应key
- 删除位置
- 删除范围
（3）unordered_map
与map的API基本相同，不过没有排序（哈希表为无序）
常用API
- constructor：也是缺省长度为100
- insert：使用insert_unique
- 插入值
- 插入范围
- erase：删除值 / 范围
- operator[]：
- 与map相同，其会使用find_or_insert，若存在返回位置，不存在插入默认值
（4）unordered_multiset
与unordered_set 基本完全相同，唯一的区别是允许相同元素，因此使用的是哈希表的insert_equal
（5）unordered_multimap
与unordered_map 基本完全相同，唯一的区别是允许相同元素，因此使用的是哈希表的insert_equal