哈希查找

哈希查找(Hash)

#1 哈希查找步骤

1. 关键字(key),经过哈希函数计算得到一个结果,这个结果叫哈希地址(addr)
2. 然后根据哈希地址(addr),将关键字存到一个一维数组下标为addr的位置
3. 此时,可能存在多个关键字(key)经过哈希函数计算得到的哈希地址(addr)相同,这种线程称为哈希冲突,这几个具有相同哈希地址的关键字称为同义词

#2 哈希函数

#2.1 构造哈希函数

构造哈希函数需要注意一下几点 :

• 哈希函数的定义域必须包含需要存储的关键字(key),而值域的范围则依赖于散列表的大小
• 哈希函数计算出来的地址应该能等概率/均匀的分布在整个地址空间.从而减少冲突的发生
• 散列函数应尽量简单,能够在较短时间内就计算出任意关键字对应的哈希地址

#2.2 常用的哈希函数

#2.2.1 直接定址法

直接取关键字的某个线性函数值为哈希地址,哈希函数为:

H(key) = a*key + b

其中,a和b为常数

不足:

• 这种方法简单,不会产生冲突,它适合关键字分布基本连续的情况,若关键字分布不连续,空位较多,造成存储空间浪费

#2.2.2 除留余数法

这是一种简单/最常用的方法,嘉定哈希表表长为m,取一个不大于m但最接近或等于m的质数p,利用一下公式把关键字转化成哈希地址:

H(key) = key % p

除留余数法关键是选好p,使每一个关键字经过哈希函数转换后等概率的映射到散列空间的任一地址,从而尽可能减少冲突的可能性

#2.2.3 数字分析法

分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

#2.2.4 平方取中法

取关键字平方后的中间几位作为散列地址。

#2.2.5 折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

#3 处理冲突的方法

#3.1 开放定址法

#3.1.1 线性探测法

冲突后，线性向前试探，找到下一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。

#3.1.2 再散列法

当通过第一个哈希函数H1(key)得到的哈希地址发生冲突时,利用第二个哈希函数H2(key)计算该关键字的哈希地址

#3.2 拉链法

对于不同的关键字可能会通过哈希函数映射到同一个地址,为了避免非同义词发生冲突,可以把所有的同义词存储在一个线性链表中,这个线性链表由其哈希地址唯一标识

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JKINeJPz-1583679651011)(https://raw.githubusercontent.com/Coxhuang/yosoro/master/20200308225803-image.png)]

在这里插入图片描述