社区首页 >专栏 >哈希相关知识再学习

哈希相关知识再学习

静默加载

发布于 2020-05-29 02:21:32

7980

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

根据关键字（Key value）至二级访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

对不通的关键字可能得到同意散列地址，即k1 != k2,而f(k1) = f(k2)，这种现象称为碰撞，也叫哈希冲突。

使用数组或者链表存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某一个元素是否存在的过程中，数据和链表都需要循环便利，而通过哈希计算，可以大大减少比较次数。

哈希使用

直接定址法

除留余数发

数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。仅仅用于适用所欲关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。

数字分析法

平方取中法

折叠法

构造哈希函数的方法很多，实际工作中需要根据不同的情况选择合适的方法，总的原则是尽可能的减少产生的冲突。

通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。

如：当关键字是整数类型时就可以用哦除留余数法；如果关键字是小数类型，选择随机书法会比较好。

哈希函数

拉链法解决冲突的做法是：将所有关键字为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互素，才能使发生冲突的同义词地址均匀分布在整个表中，负责可能造成同义词地址的循环计算。该方法是开放定址法中最好的方法之一。