哈希表

哈希表是 key-value 类型的数据结构，通过关键码值直接进行访问。通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置，哈希表可以理解为一个键值需要按一定规则存放的数组 。

• 哈希函数
• 装填因子
• 冲突

起因

假设我们存在一个简单的键值对结构，键 - 员工号，值 - 是否在岗。现在需要这样一个功能，输入员工号，返回该员工是否在岗，理想的方法是创建一个长度为 Max(员工号) 的数组，数组下标就是员工号，数组中的值用 0 和 1 对是否在岗进行区分，这样只需要 O(1) 的时间复杂度就可以完成操作，但是扩展性不强，存在以下问题。

1. 假设新进员工的员工号比 Max(员工号) 还要大，这就需要重新申请数组进行迁移操作。
2. 假设一种极端的情况，存在两个员工，员工号分别是 1 和 100000000001，这样子的话按照先前的设计思路，是会浪费很大的存储空间的。

上面两点，第一点是因为数组的固定申请大小的属性所决定，而第二点就是引入哈希表的原因，会不会存在一个方法，让一个大员工号变小而而且没有标记，哈希函数便产生，假设此处的哈希规则是除 3 取模，则员工 1 得到的哈希值是 1，员工 100000000001 得到的哈希值是 2，这样的话按照设计思路，只需要一个大小为 2 的数组便可以覆盖了，这就是哈希思想。

算法中时间和空间是不能兼得的，哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作，这取决于具体的功能要求。

哈希函数

上面的例子中哈希函数的设计很随意，但是从这个例子中我们也可以得到信息：

哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可；

并不是所有的输入都只对应唯一一个输出，也就是哈希函数不可能做成一个一对一的映射关系，其本质是一个多对一的映射，这也就引出了下面一个概念–冲突。

冲突

只要不是一对一的映射关系，冲突就必然会发生，还是上面的极端例子，这时新加了一个员工号为 2 的员工，先不考虑我们的数组大小已经定为 2 了，按照之前的哈希函数，工号为 2 的员工哈希值也是 2，这与 100000000001 的员工一样了，这就是一个冲突，针对不同的解决思路，提出以下不同的解决方法。

开放地址

开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的开放地址思想的方法有线性探测再散列，二次探测再散列，这些方法都是在第一选择被占用的情况下的解决方法。

再哈希法

这个方法是按顺序规定多个哈希函数，每次查询的时候按顺序调用哈希函数，调用到第一个为空的时候返回不存在，调用到此键的时候返回其值。

链地址法

将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到。

公共溢出区

其基本思想是：所有关键字和基本表中关键字为相同哈希值的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

装填因子α

一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为表中填入的记录数和哈希表长度的壁纸，也就是标志着哈希表的装满程度。直观看来，α越小，发生冲突的可能性就越小，反之越大。一般 0.75 比较合适，涉及数学推导。