首页 > 代码库 > 查找(五)——聊聊哈希

查找(五)——聊聊哈希

我们之前的查找要么是顺序查找,要么是折半查找,要么是基于二叉树的查找

然而,这些查找之中,元素在列表中的相对位置是随机的,与关键字之间并没有直接的关系,因此,在查找时需要通过比较来进行

现在,我们有一种牺牲空间来换取时间的方法,通过固定元素在列表中的相对位置,在关键字和元素位置之间建立直接的关系,获得一种映射表,这就是哈希表

 

所谓哈希法,就是通过建立元素位置和元素关键字之间的对应关系(即哈希函数),以后查找关键字时,就通过哈希函数来计算出元素的位置

 

当然,在这一个过程中,通过哈希函数计算的位置可能会发生冲突,这种冲突发生于创建哈希表时和查找时

 

 

以上可以总结了:

 

一所谓哈希法实际上可以分为两部分:

    1.建立哈希函数

    2.如何处理冲突

 

冲突分为两种情况:创建哈希函数时和查找时,这两种冲突情况的冲突是一样的,解决方案也是一样的

 

 

一.建立哈希函数

  书上有五种方法,简直眼花缭乱,我最烦这种枯燥的教学,不传授思想,不传授为什么,直接摆公式,摆方法,

  其实这五种方法是一个意思,哪怕还有一百种方法也是一个意思,那就是:

  根据关键字有逻辑地得出尽可能不同,尽可能均匀的数字(地址)

  1.数字分析法

  2.平方取中法

  3.分段叠加法

  4.除数余留法

  5.伪随机数法

  我就不一个一个解释了,不知道的直接看书或者百度就行

 

二.如何处理冲突

  所谓处理冲突嘛,不就是当不同的关键字通过哈希函数得出的地址是一样的(这个时候就冲突了),这个时候怎么处理,其实各种方法眼花缭乱也是一个意思,怎么样有逻辑地再找出一个不冲突的地址

  书上有四种方法:

  分别是:

  1.开放定址法,也称再散列法

  2.再哈希法(备用哈希函数)

  3.链地址法

  4.建立公共溢出区

不多解释,

 

三.哈希表的查找过程:

  1.首先通过关键字key计算出哈希函数对应的值H(key)

  2.如果H(key)为空,返回空,也就是找不到,否则,进入第三步

  3.如果找到的值等于key,返回key,也就是找到了,否则,进入第四步

  4.找到的值不等于key,那么,就进入冲突处理过程,这根据采取的冲突处理不同而不同!

 

四.复杂度分析

  如果哈希表完全没有冲突,那么时间复杂度为O(1);

  实际上,总的时间复杂度=哈希函数的时间复杂度(这个通常为O(1))+处理冲突的时间复杂度*@

    @为发生冲突的概率

 

查找(五)——聊聊哈希