一、哈希表的目的
哈希表是用在查找问题中的。
我们知道，一条数据包含了关键字和其他信息，所以一般查找问题的流程是：根据某条数据的关键字（key），在一个数据结构中（可能是线性表，也可能其他存储数据的结构），查找这条数据全部的内容。
哈希表的目的是，只要知道了要查找数据的关键字，那么就可以立刻得到存储这条数据的地址（比如顺序表的索引就可以看做地址），然后根据这个地址去到相应位置上，就得到了一条数据的全部内容。
二、哈希表是一张怎样的表
首先，哈希表可以简单认为是一个数组，它每一位都有一个索引，每个位置上存有数据，这个数据是全部的数据，既包含某条数据的关键字，也包含这条数据的其他部分。
当你想查找关键字为k的数据时，首先通过哈希函数（也称为散列函数），得到关键字为k的数据在哈希表中的索引，即index=Hash（k），然后就可以根据索引，在哈希表中找到索引index处存储的内容。
三、哈希函数和这个函数的构造方法
描述地专业一点，哈希函数是从关键字集合到索引值集合的映射。
换言之，就是通过对一个关键字k进行一波操作，得到一个索引值，所谓的【哈希函数的构造方法】，说白了就是在设计哈希函数的时候去研究这波操作怎么搞。
这里列举7种基本方法。
1.直接定址法
用式子描述，就是：index=Hash(key) = a·key + b (a、b为常数) 这里的关键字肯定是数字。
2.数字分析法
将一个关键字（比如身份证号）取其中的几位，然后做一些处理得到一个值。
有三个问题需要多提一嘴。
第一，该方法一般适用于关键字位数很多的情况，反正肯定比索引值位数多，最经典的例子就是身份证号。
第二，从关键字中取几位时，取法有讲究。要满足：各种符号在该位上出现的频率大致相同。
比如身份证号，有些位上的数字出现的频率是大致相同的，比如生日位，这个不确定性很强，所以0-9出现的频率不相上下；But，有些位不是如此，比如开头表示省的两位。如果我的所有数据都是取自某个省，那么其实开头两位都是一样的，也就是说，其他数字基本不可能出现在前两位，这样的位就不满足【各种符号在该位上出现的频率大致相同】。
第三，取出几位之后，要做什么样的处理才能得到索引值呢？
这个不一定，视具体情况而定。比如身份证号，假设我取了5位，5个数字分别为2,4,5,6,7。那么我的处理可以是2*10^4+4*10^3+5*10^2+6*10^1+7*10^0，这样就可以得到24567这个数字 ，作为索引值。
不过24567这个索引值很大，如果我的全部数据的个数也是几万这个数量级，那勉强还可以，可如果我只有80条数据，那索引值比数据总数还大，就不是一个好的构造，可以少取几位，比如取两位，这样最后得到的索引值是两位数，与数据总数在数量级上差不多，还算不错。
3.平方取中法
对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。
举个栗子。
关键字假设是1234，1234的平方是1522756，那我可以取2作为索引，当然也可以取22，取227，取52275，这个取多少，取决于哈希表有多大，比如哈希表只有80位，索引值取了52275，这不合适。
4.折叠法
第一步，将关键字自左向右分成若干个位数相等的部分，最后一部分位数可以少一点。
比如15698746，分成156 987 46三部分。
第二步，把每部分看做数字，直接相加（这个方法叫移位法）
156+987+46=1189
第三步，把得到的数字1189，从右边取几位作为索引，比如取个9，或者是取89，具体取多少也是要参考哈希表的长度。
另外，第二步还可以换种方法，叫间界叠加法。
其实就是把每部分的数字倒过来，651+789+64=xxx这样子。
5.除留余数法
index=Hash(key)=key mod p (p是一个整数)
这是很简单也很常用的办法。
关于p的取法，一般取不大于哈希表长度的最小素数。
6.乘余取整法
关键字key乘以A，取小数部分，然后乘B，取整，作为索引值。
其中，A介于0和1之间。取小数部分可以通过模1来实现。
7.随机数法
index=Hash(key) = random ( key )
这里的random是伪随机函数。
这种方法主要用于关键字长度不一样的情况，比如有的数据的关键字很长，另一些数据的关键字却很短。
四、哈希冲突的处理办法
先唠唠什么是哈希冲突。
简单来讲，如果两个不同的关键字经过哈希函数后，得到了同一个索引值，那么意味着两条数据要存到同一个位置，这显然不可以，这就叫哈希冲突。
说得专业点，哈希函数是从关键字集合到索引值集合的映射，如果这个映射不是单射，就会有哈希冲突。
那么解决哈希冲突的办法有哪些呢？这里给出四种办法。
1.开放定址法
基本思路：
如果发生了冲突，比如在索引为i的地方放了数据，之后又要在这个位置放数据，这就冲突了。
简单粗暴的解决思路是，既然这个地方有数据占用了，那索性【第二个本来应该放在这的数据】，就不和【第一次放进来的数据】抢位置了，而是选择其他空位置放。
那么如何选择其他空位置呢？这里有三种寻找空位置的办法。
（1）线性探测法
公式如下：indexi=（Hash（key）+di）mod m，i=1,2，……，m-1
其中，m是哈希表长度，确保算出来的索引值始终位于0到m-1
di是增量序列：1,2，…，m-1（听不懂往下看）
如果Hash(key)对应的索引位置没有元素，就直接存入，否则就按照上面的式子，将Hash(key)+1然后模m，得到新的索引，如果这个索引位置没有存数据，就可以直接把当前数据存入，否则就计算Hash（key）+2，模m，判断这个索引位置是否为空，若空就存入不空就算Hash（key）+3再mod m，直到找到空位置。
以上就是线性探测法的过程。
查找的时候，根据一个关键字k，算出Hash（key），但是发现这时候存的数据的关键字不是k，那就说明，有可能在哈希表构建之初，关键字为k的数据在索引为Hash(k)的地方发生了哈希冲突，所以采用线性探测法移动到别的位置了，那么如果一开始的冲突处理机制已经确定好了，那么这时候就可以按照同样的机制去找关键字为k的数据。
（2）二次探测法
indexi=(Hash(key)+di) mod m
di为增量序列，1^2，-1^2，2^2，-2^2，3^2，-3^2……，(m/2)^2，-(m/2)^2
这个过程与线性探测法基本一致，只不过发生哈希冲突后，找新的索引时，d按照序列的顺序依次取值，直到算出来的index对应的位置是空位置为止，然后把数据存到空位置里。
（注意：如果哈希表的表长不是4k+3的形式，那么可能会出现哈希表存在空位置但数据插不进去的可能。这里不做赘述了。）
（3）伪随机探测法
index=(Hash(key)+d) mod m
增量序列d使用一个伪随机函数来产生一个落在闭区间[1，m-1]的随机序列。
换言之，确定好一个伪随机函数，那么d这个序列每一项的值就是确定的，只不过可能彼此之间没什么关系，但是只要伪随机函数是确定的，那么它产生的序列就是唯一的。
（正是因为伪随机函数的这个特性，所以常应用在既想得到比较随机的序列，又想使这一随机过程可以复现的场景。这句如果不理解可跳过，浅浅拓展）
2.再哈希法
indexi=Hashi(key)
只不过，这里的Hashi(key)可以认为是一个哈希函数序列。对于一个key，先算Hash1（key），如果发生冲突，就接着算Hash2（key），直到不发生冲突时，再把数据存入。
3.链地址法（拉链法）
之前提到过，如果一开始在索引为i的地方存了数据，之后如果另一个数据也要存在这个位置，就会发生哈希冲突，因为数组的一个位置不能存两个数据。但是，如果强行就是要让多个数据存在一个位置可以吗？
这可以通过邻接表来实现（回想图的存储结构）。
只需要让数组的每个索引的位置上存储一个链表的头指针，然后所有的数据都存到链表里。即某索引位置上如果新来了一个数据，那先把数据放到一个结点里，再把这个结点就用头插法或者尾插法插到链表里，这样就可以避免哈希冲突。
4.公共溢出区法
除了哈希表之外，再建一个新的顺序表，成为溢出表。
当某个数据发生了哈希冲突，就不存到哈希表里了，直接按顺序存到溢出表里即可。
查找时，根据key计算Hash（key），即索引，然后到索引位置检查是否有数据，若没有，说明查询失败，若有数据，就检查这个数据的关键字是不是key，如果是则查询成功，不是则说明可能在构造哈希表时这里发生了哈希冲突，于是直接去溢出表里顺序查找。
注意，公共溢出区法不是一个孤立的办法，也可以和其他方法结合，比如当使用线性探测法把哈希表的所有位置都插满之后，剩下的数据没处可插，就可以放到溢出表里。
好了，以上就是哈希表的主要知识点了，欢迎各位纠错指正！
祝你学会~
标签：知识点,Hash,哈希,索引,可速通,关键字,key,数据 From： https://blog.csdn.net/FulcrumAC/article/details/144246430