个人博客地址 http://dandanlove.com/
在平时工作和源码学习的过程中经常遇到哈希相关的问题，每次都会上网找资料回忆哈希相关的知识点。趁这机会记录下来，防止以后又忘记了！！
哈希表
根据关键字（Key value）至二级访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
哈希冲突
对不通的关键字可能得到同意散列地址，即k1 != k2,而f(k1) = f(k2)，这种现象称为碰撞，也叫哈希冲突。
为什么需要哈希
使用数组或者链表存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某一个元素是否存在的过程中，数据和链表都需要循环便利，而通过哈希计算，可以大大减少比较次数。
几种常见的哈希函数（散列函数）的构造方法
-
直接定址法：取关键字或者关键字的某个线性函数值为散列地址。例如：H(key) = key,H(key) = a*key + b,其中a，b为常数。
直接定址法 -
除留余数发：取关键字被某个不大于散列长度m的数p求余，得到的作为散列地址。例如：H(key)=key%p,p < m。
除留余数发 -
数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。仅仅用于适用所欲关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
数字分析法 -
平方取中法：先计算出关机子的平方值，然后取平方值中间几位作为散列地址。随机分布的关键字，得到散列地址也是随机分布的。
平方取中法 -
折叠法（叠加法）：将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。用于关键字位数比较多，并且关键字中每一位上数字分布大致均匀。
折叠法 - 随机数法：选择一个随机函数，把关键字的随机函数值作为它的哈希值。通常关键字的长度不等时采用这种方法。
构造哈希函数的方法很多，实际工作中需要根据不同的情况选择合适的方法，总的原则是尽可能的减少产生的冲突。
通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。
如：当关键字是整数类型时就可以用哦除留余数法；如果关键字是小数类型，选择随机书法会比较好。
哈希函数
链接法（拉链法）
拉链法解决冲突的做法是：将所有关键字为hash相同的结点链接在同一个单链表中。
若选定的散列表长度为吗，则可将散列表定义为一个由m个头指针组成的指针数组T[0...m-1].
凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。
T中各个分量的初值值均为空指针
在拉链法中，装填因子a可以大于1，但一般均取a<=1。
开放定址发（再散列法）
基本思想：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1任然冲突，再以p为基础，产生另一个哈希地址p2，...，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。
这种方法有一个通用的再散列函数形式：Hi = (H(key) + di) % m, i = 1,2,,4,...,n。其中H（key)为哈希函数，m为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
用开放定址法解决冲突的做法是：
当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，知道找到给定的关键字，或者碰到一个开放地址（即该地址单元为空）为止（若要插入，在探测到开放的地址，则可将待插入的新结点存入该地址单元）。查找时探测到开放地址则表明无待查的关键字，即查找失败。
简单的说：当发生冲突时，使用某种探测（亦称探测）技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列表地址总能找到。
按照形成探查序列的方法不同，可将开放地址发区分为线性探查法、二次探查法、双重散列法等。
-
线性探查法：hi=（h（key） + 1） % m， 0 <= i <= m-1。
基本思想是：探查时从地址d开始，首先探查T[d],然后依次探查T[d+1],...,直到T[m-1],此后又循环到T[0],T[1],...,直到有空余地址或者到T[d-1]位为止。
这种方法的特点是：冲突发生时，顺查看表中下一单元，知道找出一个空单元或者查遍全表。
-
二次探测再散列法：hi=（h(key) + i*i）% m, 0 <= i <= m-1。
基本思想是：探查时从地址d开始，首先探查T[d],然后依次探查T[d+1^2],T[d+2^2],T[d+3^2],...等，直到探查到有空余地址或者到T[d-1]为止。
缺点是无法探测到整个散列空间。
-
双重散列法：hi=(h(key) + i*h1(key))%m, 0 <= i <= m-1。
基本思想是：探查时从地址d开始，首先探查T[d],然后依次探查T[d+h1(d)],T[d+2*h1(d)],...,等。该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。
定义h1(key)的方法比较多，但无论采用什么方法定义，都必须使h1（key)和值和m互素，才能使发生冲突的同义词地址均匀分布在整个表中，负责可能造成同义词地址的循环计算。
该方法是开放定址法中最好的方法之一。
建立公共溢出区
这种方法的基本思想是：将hash表分为基本表和溢出表两部分，凡是基本表发生冲突的元素，一律填入溢出表。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1(key) i=1,2,3,,,,k
当哈希地址Hi=RH1(key)发生冲突时，再计算Hi=RH2(key),,,,直到冲突不再产生。这种方法不易产生聚焦，但增加了计算时间。
参考文章: 重温数据结构：哈希 哈希函数 哈希表
文章到这里就全部讲述完啦，若有其他需要交流的可以留言哦！！
想阅读作者的更多文章，可以查看我 个人博客 和公共号：
