一、unordered 关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器（set、map、multiset、multimap）在查询时效率可到到 O(logN) ，每次查找都需要比较节点的左右子树，当要查找的数据刚好位于叶子节点处时，就要比较树的高度次，当树的高度较大时，查找效率也不理想。
理想的查找效率是：1次就可以将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，它们虽然不能保证每次都能1次找到数据，但是它们需要进行的比较次数比红黑树少的多。这四个容器底层是运用了哈希结构，因为unordered容器与红黑树结构的容器使用方式基本蕾西，所以下面就只简单列举一下 unordered_map 的使用方式。
unordered_map 的使用
1.构造
unordered_map<int, int> myMap; // 定义一个空的 unordered_map
unordered_map<string, int> myStringMap = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
2.容量
bool empty() const ：检测unordered_map 是否为空
size_t size() const ：获取unordered_map 的有效元素个数
3.迭代器
begin ：返回unordered_map第一个元素的迭代器
end ：返回unordered_map最后一个元素下一个位置的迭代器
cbegin ：返回unordered_map第一个元素的const迭代器
cend ：返回unordered_map最后一个元素下一个位置的const迭代器
4.元素访问
operator[] ：返回与key对应的value，没有默认值
5.查询
iterator find(const K& key) ：返回key在哈希桶中的位置
size_t count(const K& key) ：返回哈希桶中关键码为key的键值对的个数
6.修改
insert ：向容器插入键值对
erase ：删除容器中的键值对
void clear() ：清空容器中有效元素的个数
void swap(unordered map&) ：交换两个容器中的元素
7.桶操作
size_t bucket_count()const ：返回桶的总个数
size_t bucket_size(size_t n)const ：返回n号桶中有效元素的总个数
size_t bucket(const K& key) ：返回元素key所在的桶号
二、哈希结构
1.概念
在红黑树(平衡树)中，查找一个元素时，需要经过关键码的多次比较，时间复杂度为 O(logN)；而在顺序结构中，时间复杂度为 O(N)。搜索的效率取决于元素比较的次数。
而哈希结构可以近乎做到理想的搜索方式：不进行任何比较，1次直接找到目标元素
通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时，根据关键码就可以很快找到该元素。
每一个存储位置都有对应的下标，但是下标个数是有限的，而且关键码可以是任意的，此时就需要通过哈希函数，将关键码与下标建立映射关系（比如这里就是取 关键码/10 的余数），再将元素存放当对应的位置（25/10余5，所以存放到下标为5的位置）。
搜索元素时，也是将关键码进行同样的计算，求得存储位置（下标），就能直接搜索到，不需要进行元素之间的比较（事实上还是需要一定程度的比较的，后面会提到）。
上述的哈希函数设置为：hash(key) = key % capacity（capacity为存储元素底层空间总的大小）
还是上述这张表，当我想继续插入关键码为17的元素，会出现什么问题？根据哈希函数，关键码为17，存储下标为7，但当前位置已存储了元素7，不能继续存储，此时出现的情况就叫哈希冲突。
2.哈希冲突
对于不同元素的关键码，通过相同的哈希函数计算出相同的哈希地址，这种现象称为哈希冲突。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。上述元素7和17就是一对同义词
那么发生哈希冲突该如何处理呢？
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
3.哈希函数
哈希函数的设计遵循以下原则：
a. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表(哈希表)允许有x个地址 时，其值域必须在0到x-1之间
b. 哈希函数计算出来的地址能均匀分布在整个空间中
c. 哈希函数应该比较简单
常见哈希函数：
1.直接定址法：
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要知道关键字的分布情况
使用场景：适合查找小且连续的关键字
2.除留余数法：
设散列表中地址数为m，取一个不大于m但接近或等于m的质数p作为除数
：Hash(key) = key% p(p<=m)
优点：简单、均匀
缺点：性能依赖表大小
使用场景：大范围且不连续的关键字
3.平方区中法：
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址
使用场景：不知道关键字的分布且位数不大
4.折叠法
将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
使用场景：不知道关键字的分布且位数较大
5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)
使用场景：关键字长度不等
哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是终究无法避免哈希冲突。