哈希表/散列表
Hash table：
1、哈希表是一种用于以常数平均时间进行插入和查找的数据结构，不支持排序以及需要依靠排序来实现的操作
2、哈希表的主要思想是通过散列函数将关键字映射到数组的某个下标位置，进而来实现常数时间的查找
3、由于散列函数可能将不同的关键字映射到同一个位置，这种情况被称为冲突
4、哈希表主要面临两个问题：散列函数的选择和冲突的解决
5、为了散列均匀，保存元素的数组的长度为质数
质数就是除了1和它本身之外,再也没有整数能被它整除的数.比如：2..3.5.7.11.13.17.19.23.39.31…………………………
素数就是质数.质数只外的数称为合数.合数比如：4.6.8.16.32.64.72……………………………………
但是注意,1既不是素数也不是合数.
6、散列函数
针对整数、表长有限、字符转换、质数
7、冲突解决
1）分离链接法/开链法（STL中hash table的实现方法）
将散列到同一个位置的所有元素保留到一个表中
2）开放定址法
开放定址法是一种不需要链表来解决散列冲突的方法，其基本思想是：如果有冲突发生，就尝试选择另外的存放单元，直到找出空的单元为止。
开放定址法又包括三种方法：线性探测法、平方探测法、双散列
4、线性探测法
当冲突时，一一往下找，直到找到空位，如果到达尾端，则从头开始继续找
5、平方探测法/二次探测法
如果假设表格大小为质数（prime），而且永远保持负载系数在0.5以下（超过0.5就重新配置表格），则可以保证每插入一个新元素所需要的探测次数不多于2
6、双散列
其中，R为小于table size的素数
比如下图中，令R=7
3）再散列
基本思想：对于使用平方探测的开放定址法，如果表的元素填得太满，那么操作的运行时间将开始消耗过长，且insert操作可能会失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决方法是建立另外一个大约两倍大的表（而且使用一个新的散列函数），扫描整个原始散列表，计算每个元素的新散列值，并将其插入到新散列表中的相应位置
4）可扩散列
这种散列方法主要是针对数据量太大，以至于装不进主存的情况，此时主要考虑的是检索数据所需的磁盘存取次数
eg. 假设数据由6个比特整数组成，如图所示，第一行为存入内存中的内容，每次在下面对应竖框中查找为一次磁盘操作。
8、hash table构成的四个新数据结构：
hash_set、hash_multiset、hash_map、hash_multimap
1）STL中，set、map、multiset、multimap以RB tree为底层实现，hash_set、hash_multiset、hash_map、hash_multimap以hash_table为底层实现
2）由于hash_set的操作接口，hash都提供了，所以几乎所有的hash_set操作行为都只是转调用hash_table的函数操作，hash_map同理
3）由于RB tree有自动排序功能而hash table没有，因此set、map、multiset、multimap的元素有自动排序功能，而hash_set、hash_multiset、hash_map、hash_multimap没有
4）map有键值和实值，而set只有一个值
5）由于STL中的hash table只能处理char*、char、short、int、long及其相应类型，因此hash_set、hash_multiset、hash_map、hash_multimap也只能处理这些类型，诸如string这些其他类型不能处理，会报错