共计 2089 个字符，预计需要花费 6 分钟才能阅读完成。
前言：面试经常被问到 ” 你了解哈希吗？”，今天就来做一下梳理总结
1. 什么是哈希函数
散列技术是把 记录的存储位置和它的关键字之间 建立一个确定的对应关系 f，使每个关键字 key 对应一个 存储位置 f(key),
而这个 f 函数就是哈希函数
2. 什么是哈希表
采用哈希函数把记录存储在一块 连续的存储空间中，这块连续的存储空间就称为 散列表或者哈希表（hash table）。
key 是关键字，f(key) 是存放记录的散列地址。
3. 哈希表查找的适用范围
散列技术是一种存储方法，也是一种查找方法。最适用的范围是查找与给定关键字 相等的记录。
4. 哈希表是怎么通过查找的关键字 key 定位到数据的
根据指定的 key，用哈希函数进行运算，等到的就是存放数据的地址。
好的哈希函数要符合：计算时间要比其他查找技术用时少，散列地址分布均匀
（1）直接定址法：适用于 事先知道关键字的分布情况，且查找表较小并连续。
f(key) = a * key +b
举个例子，比如要统计 80 后出生年份的人口数，此时函数为 f(key) = key -1980
(2)数字分析法: 适用于 关键字位数比较大的情况并预先知道关键字的分布且若干位分布较均匀
关键字：抽取，从关键字中抽取一部分来计算散列存储的位置方式
比如手机号前三位是接入号，中间四位表示用户的归属地，后四位才是真正的用户号
可以对后四位进行反转（1234->4321）, 右环位移（1234->4123）等等方法
（3）平方取中法：适用于 不知道关键字分布，而位数不是很大的时候
假设关键字是 1234，那它平方就是 1522756，再抽中间 3 位 227，用作散列地址。（4）折叠法：适用于 事先不知道关键字的分布，适合关键字位数较多的情况
它是将关键字 从左到右分割成 位数相等的几部分（最后一部分可以短一些），然后将这几部分用加法求和，并且按照散列表的表长，取最后几位作为散列地址
举例：9876543210，散列表长度为 3 位，把它分为四组 987,654,321,0，然后叠加求和 987+654+321+0 = 1962
取后面三位 即 962（5）除留余数法（此方法为最常用的构造散列函数的方法）
f(key) = key mod p (p<=m)
mod 就是求余数的意思，这个方法不仅可以对关键字取模，也可以在进行折叠，平方取中后再取模
本方法的关键在于 选取 合适的 p，如果 p 选的不好就容易产生同义词
p 的选取方法：如果散列表的长度为 m，则 p <= m(最好接近 m) 的最小质数或者不包含小于 20 质因子的合数。(6)随机数法：适用于 关键字的长度不等的场景
选择一个随机数，取关键字的随机函数值作为它的散列地址即，f(key) = random(key)
在采用不同的哈希函数的时候主要考虑以下几点：
关键字的长度
散列表的大小
计算散列地址所需的时间
关键字的分布情况
记录查找的频率
5. 为什么会有哈希冲突，怎么解决哈希冲突
当 关键字 key1 不等于 key2，但是分别用 f(key1) f(key2) 等到两个相同的地址，这种现象就叫做冲突，并把 key1 和 key2 称为这个散列函数的同义词。
怎么解决冲突？
（1）开放地址法：即一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到并将记录存入。
公式：f(key) = (f(key) + di) mod m (di = 1,2,3,......, m-1)我们把这种解决冲突的开放地址法称为线性探测法，像碰到 key1 和 key2 经过哈希函数计算后并没有冲突，但是还要争夺一个地址的情况称为堆积。
还有一种情况，当发生冲突后，当前地址的后续都没有空位置，但是前面还有一个空位，尽管可以继续往后 + 1 来找到空位置，但是效率很差。
所以在线性探测法的基础上进行二次探测法, 即，对 di 进行平方，这样它就可以往回找了
f(key) = (f(key) + di) mod m (di = 1^2, -1^2,2^2,-2^2m…, q^2, -q^2, q <= m/2)
(2)再散列函数法
再散列地址法就是事先准备多个散列函数，比如折叠，平方取中，除留余数，每当发生散列地址冲突的时候，就换一个散列函数计算
这种方法能够使关键字不聚集，但是也相应增加了计算的时间
（3）链地址法
就是把所有关键字为同义词的记录存放在一个单链表中，散列表只存储这个链表的头指针
这样的话无论有多少个冲突，都只是在当前位置给单链表增加节点，但是同时也带来了查找时需要遍历单链表的性能损耗
（4）公共溢出区法
把冲突的值用新的一张溢出表来保存，在查找的时候，先和基本表相应的位置进行比对，如果相等，则查找成功
不相等则到溢出表去顺序查找。如果相对基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能还是可以的
6. 哈希表查找的时间复杂度是多少（没有哈希冲突的理想状态下），在有哈希冲突的情况下，散列查找的平均查找时间取决于什么呢？
散列表是几乎所有查找中效率最高的，因为它的时间复杂度是 o(1)
在非理想状态下 散列函数的平均查找时间取决于
（1）散列是否均匀
（2）处理冲突的方法：线性探测法可能会产生堆积，显然没有二次探测法好，而链地址发处理冲突则不会产生堆积，因而具有更佳的平均查找性能。
参考来源：《大话数据结构》
