哈希
1.无序的关联式容器（unordered_map&unordered_set）
unordered_map与unordered_set几乎与map与set是一样的，只是性能unordered_map与unordered_set比map与set更优一些。还有就是unordered_map与unordered_set是无序的，map与set是有序的（会将数据进行排序）。
unordered_map：官方实现
unordered_set：官方实现
unordered_map、unordered_set与map、set对比与联系：
- 都可以可以实现key和key/value的搜索场景，并且功能和使用基本一样。
- map/set的底层是使用红黑树实现的，遍历出来是有序的，增删查改的时间复杂度是0(logN)
- unordered_map/unordered_set的底层是使用哈希表实现的，遍历出来是无序的，增删查改的时间复杂度是O(1)(不是1次，是常数次)，说明性能比map/set更优一些
- map和set是双向迭代器，unordered_map和unorded_set是单向迭代器。
- unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
2.哈希表
2.1哈希概念：
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较 。 顺序查找时间复杂度为 O(N) ，平衡树中为树的高度，即 O(log N)，搜索的效率取决于搜索过程中元素的比较次数。※理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素 。解释说明插入和搜索：当向该结构中：插入元素根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较， 若关键码相等，则搜索成功该方式即为哈希 ( 散列 ) 方法， 哈希方法中使用的转换函数称为哈希 ( 散列 ) 函数，构造出来的结构称 为 哈希表 (Hash Table)( 或者称 散列表 )。举例：数据集合 {1 ， 7 ， 6 ， 4 ， 5 ， 9} ；哈希函数设置为： hash(key) = key % capacity ;key为待插入的值（1 ， 7 ， 6 ， 4 ， 5 ， 9）capacity为存储元素底层空间总的大小（申请的存储空间的容量）。
但是：这种插入看似合理，但是也有很大的弊端， 如果插入11呢?hash(11)=11%10=1,1映射过去，1的位置已经被占了。这个问题就是 哈希冲突？2.2哈希冲突对于两个数据元素的关键字key_i和 key_j(i != j)，有key_i != key_j，但有：Hash(key_i) == Hash(key_j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突 或哈希碰撞 。引起哈希冲突的一个原因可能是： 哈希函数设计不够合理 。哈希函数设计原则 ：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
2.3常用的哈希函数：2.3.1 . 直接定址法 --( 常用 )取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key + B优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况2.3.2. 除留余数法--(常用)设散列表中允许的 地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数： Hash(key) = key% p(p<=m), 将关键码转换成哈希地址2.3.3 . 平方取中法 --( 不常用 )假设关键字为 1234 ，对它平方就是 1522756 ，抽取中间的 3 位 227 作为哈希地址；再比如关键字为 4321 ，对它平方就是 18671041 ，抽取中间的 3 位 671( 或 710) 作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况2.3.4 . 折叠法 --(不常用 )折叠法是将关键字从左到右分割成位数相等的几部分 ( 最后一部分位数可以短些 ) ，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突2.4哈希冲突解决方法：解决哈希冲突两种常见的方法是：闭散列和开散列2.4.1 闭散列闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。
- 线性探测 ： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，一次只前进一个
- 二次探测 ： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。一次前进i^2个
2.4.2 开散列
开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。所以这个哈希表也就是一个存储节点指针的指针数组。
开散列中每个桶中放的都是发生哈希冲突的元素 。
