哈希相关知识再学习

在平时工作和源码学习的过程中经常遇到哈希相关的问题，每次都会上网找资料回忆哈希相关的知识点。趁这机会记录下来，防止以后又忘记了！！

哈希表

根据关键字（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),,,,直到冲突不再产生。这种方法不易产生聚焦，但增加了计算时间。

参考文章: 重温数据结构：哈希 哈希函数 哈希表