哈希基础概念即使用（C++）
目录
1. unordered系列关联式容器
1.1 unordered_map
1.1.1 unordered_map的文档介绍
1.1.2 unordered_map的接口说明
1. unordered_map的构造
2. unordered_map的容量
3. unordered_map的迭代器
4. unordered_map的元素访问
5. unordered_map的查询
6. unordered_map的修改操作
7. unordered_map的桶操作
1.2 unordered_set
1. unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log_2 N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset大家可查看文档介绍。
1.1 unordered_map
1.1.1 unordered_map的文档介绍
unordered_map在线文档说明（大家复制下面的链接就可以了）：
http://www.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map
我总结一下几点：
1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于唯一的标识元素，而映射值是一个对象，其内容与此 键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。
6. 它的迭代器至少是前向迭代器。
1.1.2 unordered_map的接口说明
1. unordered_map的构造
unordered_map<string, string> hash;这就构造好了，跟map是非常相似的。
2. unordered_map的容量
hash.insert(make_pair("苹果", "apple"));//插入//检查是否为空cout << hash.empty() << endl;//输出结果false//检查有效元素个数cout << hash.size() << endl;//输出结果13. unordered_map的迭代器
//迭代器unordered_map<string, string>::iterator it = hash.begin();while (it != hash.end()){cout << it->second << endl;it++;}//迭代器constunordered_map<string, string>::const_iterator cit = hash.cbegin();while (cit != hash.cend()){cout << cit->second << endl;cit++;}运行截图：
4. unordered_map的元素访问
cout << hash["苹果"] << endl;
注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶 中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中， 将key对应的value返回。
比如：
hash["香蕉"] = "banana";cout << hash["香蕉"] << endl;我们的unordered_map中其实并没有香蕉，但我们这样操作后，会给hash里面添加上香蕉
运行截图：
5. unordered_map的查询
cout << (hash.find("苹果"))->second << endl;cout << hash.count("苹果") << endl;运行截图：
注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1
6. unordered_map的修改操作
代码：
hash.insert(make_pair("苹果", "apple"));hash.insert(make_pair("香蕉", "banana"));hash.insert(make_pair("橘子", "orange"));unordered_map<string, string>::iterator it = hash.begin();while (it != hash.end()){cout << it->second << endl;it++;}cout << "--------------------------------------------------" << endl;hash.erase("橘子");it = hash.begin();while (it != hash.end()){cout << it->second << endl;it++;}cout << "--------------------------------------------------" << endl;unordered_map<string, string> hash1;hash1.swap(hash);it = hash1.begin();while (it != hash1.end()){cout << it->second << endl;it++;}cout << "--------------------------------------------------" << endl;hash1.clear();cout << hash1.size() << endl;运行截图：
7. unordered_map的桶操作
hash.insert(make_pair("苹果", "apple"));hash.insert(make_pair("香蕉", "banana"));hash.insert(make_pair("橘子", "orange"));cout << hash.bucket_count() << endl;cout << hash.bucket_size(0) << endl;cout << hash.bucket("苹果") << endl;运行截图：
通过以上的代码，我们不难发现，除了多出来的哈希桶部分，unordered_map和map的用法几乎都是一样的，毕竟我们开头也总结过，两则在使用上几乎没有差别，两者的最大区别是在底层结构上。
1.2 unordered_set
参见unondered_set文档说明：
http://www.cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set
我们就不多复述了，跟set也是大差不差，无非也会多一个哈希桶的部分。
接下来的底层实现我们会在下一篇文章里详细讲解，我们还会手撕闭散列的开放定址法的哈希表。
