数据结构 哈希表
什么是哈希表
Hash 表也称散列表，也有间接译作哈希表，Hash 表是一种依据关键字值（key – value）而间接进行拜访的数据结构。
它基于数组，通过把关键字映射到数组的某个下表来放慢查找速度，然而又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是 O(N)的工夫级，然而对于哈希表来说，只是 O(1)的工夫级。
留神，这里有个重要的问题就是如何把关键字转换为数组的下标，这个转换的函数称为哈希函数（也称散列函数），转换的过程称为哈希化。
个别哈希表都是用来疾速判断一个元素是否呈现在汇合中。
图片
哈希函数
它把一个大范畴的数字哈希（转化）成一个小范畴的数字，这个小范畴的数对应着数组的下标。应用哈希函数向数组插入数据后，这个数组就是哈希表。
哈希抵触
链地址法 –（拉链法）
这种办法的根本思维是将所有哈希地址为 i 的元素形成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因此查找、插入和删除次要在同义词链中进行。链地址法实用于常常进行插入和删除的状况。
线性探测法
长处：易于施行；总是找到一个地位（如果有）；当表不是很满时，均匀状况 下的性能十分好。
毛病：表的相邻插槽中会造成“集群”或“集群”键；当这些簇填满整个阵列的大部 分时，性能会重大降落，因为探针序列执行的工作实际上是对大部分阵列的穷举搜寻。
哈希表的长处
能够像数组一样通过下标随机拜访。
补救了数组只能通过整数索引拜访的缺点。
哈希表的毛病
每次存取数据之前要通过散列函数计算对应的散列值，耗费了更多内存。
装载因子 是散列表性能的衡量标准之一。因为散列表实际上还是数组，所以能承载的数据是无限的，当哈希表存储的数据超过数组索引的长度时则必然会呈现散列抵触。
常见的三种哈希构造
当咱们想应用哈希法来解决问题的时候，咱们个别会抉择如下三种数据结构。
数组
set（汇合）
map(映射)
在 C ++ 语言中，实现在 C ++ 中，set 和 map 别离提供了以下三种数据结构，其底层实现以及优劣如下表所示：
图片
红黑树是一种均衡二叉搜寻树，所以 key 值是有序的，但 key 不能够批改，改变 key 值会导致整棵树的错乱，所以只能删除和减少。
图片
std::map 和 std::multimap 的 key 也是有序的（这个问题也常常作为面试题，考查对语言容器底层的了解）。
当咱们要应用汇合来解决哈希问题的时候，优先应用 unordered_set，因为它的查问和增删效率是最优的，如果须要汇合是有序的，那么就用 set，如果要求不仅有序还要有反复数据的话，那么就用 multiset。
那么再来看一下 map，在 map 是一个 key value 的数据结构，map 中，对 key 是有限度，对 value 没有限度的，因为 key 的存储形式应用红黑树实现的。
总结
总结一下，当咱们遇到了要疾速判断一个元素是否呈现汇合里的时候，就要思考哈希法。
然而哈希法也是就义了空间换取了工夫，因为咱们要应用额定的数组，set 或者是 map 来存放数据，能力实现疾速的查找。
本文由博客一文多发平台 OpenWrite 公布！