哈希表概述
本文对哈希表进行大体上的概述和分析，如果你之前没有学过相关知识，可以参考哈希表以及哈希表这两篇文章，有详细的例子介绍，本文只提供快速回忆和浏览。
一、什么是哈希表？
哈希表本质就是支持随机查询的数组，即可以根据关键字快速查找值的一种数组，也就是散列表。哈希表实现的关键就是哈希函数，所谓的哈希函数是一种建立查询表的方法，它将 key 值映射为一种索引号的方法。
二、为什么要使用哈希表？
我们可以利用 key 关键字，就可以快速的找到我们想要的 value 值，而不需要循环遍历比较整个数组。例如假如你有一组数据（学号，姓名，电话号），如果将这组数据存在一个数组中，这时假如你想要查找学号为 001001001 的学生姓名和电话，你就不得不依次比较数组匹配你的学号然后取出你想要的数据，但是如果我们将学号映射为一个哈希索引，理论上就可以一次取出想要的数据。
三、如何构造哈希表？
-
直接定址法：取关键字或关键的某一个线性函数值为哈希地址。即：Hash(key)=key或者Hash(key)=a*key+b。这种构造方法下由于地址集合和关键字集合大小一样，所以并不会有冲突的发生，但是这种方法并不常用。
-
除留余数法：取关键字被某一个不大于哈希表长 mmm 的数 ppp 除后所余得的数为哈希地址。即
Hash(key)=key MOD p,p<=m(m为哈希表长)。这种方法比较简单也很常用。 -
数字分析法：就是取关键字的若干位数组成哈希地址。当然我们在取的时候要对位数进行分析，尽量减少冲突。
-
平方取中法：取关键字平方后的中间若干位组成哈希地址。相比于数字分析法优点在于一个数平方之后的中间的几位数和原来的数都有关，因此哈希地址是随机的。
四、如何解决哈希冲突？
哈希冲突：即不同key值产生相同的地址，H(key1) = H(key2) ；
解决冲突的方法：
（1）开放地址法：HiH_iHi = (Hash(key)+di(Hash(key)+d_i(Hash(key)+di) MOD mmm
其中：Hash(key)为哈希函数，di为增量序列，m为哈希表长：
-
di=1,2,3,4,5…,m-1时称线性探测再散列；
-
di=12,−12,22,−22..........,+k2,−k2(k<=m/2)1^2 ,-1^2 ,2^2,-2^2..........,+k^2,-k^2 (k<=m/2)12,−12,22,−22..........,+k2,−k2(k<=m/2)称之为二次探测再散列（平方探测在散列），其中正负号表示向右或者向左查找；
-
did_idi 伪随机数序列，称之为随机探测在散列。
（2）再哈希法：准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……；
（3）链地址法：产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据；
（4）公共溢出区法：建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
五、哈希表如何查找？
-
理想情况下我们根据关键字key,通过造表时候的哈希函数求得哈希地址，该表此位置上的记录的关键字与我们给定的关键字key相等，则查找成功。
-
但是如果有冲突，即该表此位置上的记录不是我们要查找的记录，则根据造表时候设定的冲突处理方法寻找“下一个地址”，一直到哈希表的某一个位置为“空”或者表中记录的关键字为我们给定的关键字key。
参考博客：
https://blog.csdn.net/u011109881/article/details/80379505
https://zhuanlan.zhihu.com/p/30121142