散列技术是一种查找技术,而且是一种"一步到位"的查找技术。用散列技术查找的时候,一开始存储元素就按照函数f所对应的规律去存储元素, ,使得存进去的元素key的位置是f(key),这样用函数f查找的时候才能奏效.所以说散列技术既是一种查找技术,也是一种存储技术。这里的函数f就叫散列函数(哈希函数),采用散列技术所建立的元素存储空间就是散列表(哈希表),元素的存储位置就叫散列地址(哈希地址)。
一、hashtable 1、节点定义优点：简化了比较过程 效率大大提高.
缺点：1.散列技术不适合集合中重复元素很多的情形,因为这样的话同样的key,就会对应很多index,比如用性别查找一个班的学生。
2.散列技术不适合范围查找 也不适合查找最大值,最小值。这些都无法从散列函数中计算出来.
3.散列函数需要很好的设计,应该保证简单 均匀 存储效率高
4.可能有不同的元素被映射到相同的位置(即有相同的索引) 。因为元素个数大于array 容量。这便是所谓的“碰撞(ollision)”问题。解决碰撞问题的方法有许多种，包括线性探测(linearprobing) 、二次探测(quadratic probing) 、开链(separate chaining) 等做法。每一种方法都很容易，导出的效率各不相同---与 array的填满程度有很大的关连。
以开链法( separate chaining) 完成hash table 的图形表述。称hash table 表格内的元素为桶子(bucket) ,此名称的大概意义是，表格内的每个单元涵盖的不只是个节点(元素)，甚且可能是一“桶”节点。
templatestruct __hashtable_node __hashtable_node* next; value val; };
bucket 所维护的linked list， 并不采用STL的1ist或slist,而是自行维护上述的hash table node。至于buckets 聚合体则以vector完成，以便有动态扩充能力。
2、数据结构模板参数
在
3、构造与内存管理
空间配置
HashTable里面定义了一个专属的节点配置器,用来更好的以结点为单位开辟空间
节点配置与释放函数
当我们初始构造一个拥有50个节点的hash table 如下:
这个构造函数有三个参数,第一个表示要构造哈希表结点多少,第二个是散列函数,即计算元素位置的函数型别第三个是判断键值是否相等的方法,看看构造函数具体如何执行
本质上是调用了initialize_buckets,再看一下initialize_buckets是如何执行的
next_size(n)函数返回质数表中的接近但是大于n的质数。可以看到在initialize_buckets中先计算了接近n的质数buckets空间大小,然后在里面都填充了类型为node*的空指针。
元素地址求解函数bkt_num求解元素地址就是求出元素位于哪一个bucket内,这本来是hash_function的任务,SGI把这个任务封装了一层,先交给bkt_num()，再由此函数调用hash_function 取得一个可执行取模运算的数值。为什么要这么做?因为有些元素比如字符串,无法直接拿来对hashtable的大小进行取模运算。这个时候就要通过bkt_num函数先进行转换。
上面所说的调用的
STL set多半以RB-tree为底层机制。SGI则是在STL标准规格之外又提供了hash_set， 以hashtable 为底层机制。由于hash_ set 所供应的操作接口hashtable都提供了，所以几乎所有的hash_set操作行为，都只是转调用hashtable的操作行为而已。
RB-tree有自动排序功能而hashtable没有，反应出来的结果就是，set 的元素有自动排序功能而hash_set 没有。set的元素不像map那样可以同时拥有实值(value) 和键值(key) ， set元素的键值就是实值，实值就是键值。这一点在hash_set中也是一样的。hash_set 的使用方式，与set完全相同。
hashtable 有些无法处理的型别(除非用户为那些型别撰写hash function)。凡是hashtable无法处理者，hash set也无法处理。
hash_multiset的特性与multiset完全相同，唯-的差别在于它的底层机制是hashtable。也因此，hash_ multiset 的元素并不会被自动排序。hash_multiset和hash_set 实现上的唯一差别在于,前者的元素插人操作采用底层机制hashtable的insert_equal()， 后者则是采用insert_unique()。hash_multiset 的使用方式与hash_set完全相同。
SGl在STL标准规格之外，另提供了一个所谓的hash_map,以hashtable为底层机制.由于hash_map所供应的操作接口，hashtable都提供了,所以几乎所有的hash_map操作行为，都只是转调用hashtable的操作行为而已.运用map,为的是能够根据键值快速搜寻元素.这一点不论其底层是RB-tree或是hashtable, 都可以达成任务。但是RB-tree 有自动排序功能而hashtable没有，反应出来的结果就是，map的元素有自动排序功能而hash_map没有。
- 插入操作：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 存放key和value在桶内
- 取值过程：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 比较桶内元素与key是否相等 -> 取出相等纪录的value
map的特性是每一个元素都同时拥有一个实值(value)和一个键值(key) .这一点在hash_map中也是一样的。hash_map的使用方式和map完全相同。hashtable有些无法处理的型别(除非用户为那些型别写hash function。凡是hashtable无法处理者，hash_map也无法处理。
hash_multimap 的特性与multimap 完全相同，唯一的差别在于它的底层机制是hashtable.因此hash_multimap的元素并不会被自动排序。hash_multimap和hash_map 实现上的唯一差别在于,前者的元素插人操作采用底层机制hashtable的insert_ equal()， 后者则是采用insert_unique()。
四、unordered_map与unordered_setSTL中hash_map扩容发生什么？
hash table表格内的元素称为桶（bucket),而由桶所链接的元素称为节点(node),其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。
向前操作：首先尝试从目前所指的节点出发，前进一个位置（节点），由于节点被安置于list内，所以利用节点的next指针即可轻易完成前进操作，如果目前正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点。
什么时候扩容?
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候，就要自动扩容。扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。
unordered_map约等于hash_map，unordered_set约等于hash_set。
最初的 C++ 标准库中没有类似 hash_map(hash_set) 的实现，但不同实现者自己提供了非标准的hash_map(hash_set)。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。从 C++ 11 开始，hash_map(hash_set) 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered_map(unordered_set)。这个名字其实更具描述性，因为它暗示了该类元素的无序性。
