44哈希查找 ◇思考:分析前面介绍过的各种查找方法 算机软件基础 的共同点,考虑是否有突破常规的高效率 查找方法? 提示:在元素的存放位置上动动脑筋, 使查找效率大大提高
计 算 机 软 件 基 础 4.4 哈希查找 ❖ 思考：分析前面介绍过的各种查找方法 的共同点，考虑是否有突破常规的高效率 查找方法？ ❖ 提示：在元素的存放位置上动动脑筋， 使查找效率大大提高
2爱裂 哈希表的概念及建立 1.哈希表的有关概念 (1)哈希函数 算机软件基础 哈希函数是指对于线性表中各个元素所建 立的关键字值与其在一维数组中存放位置之 间的函数(对应关系),其形式为: addr(ai)=H(ki) 其中,H为哈希函数名,a为线性表中的 第个元素,k为第个元素的关键字值
计 算 机 软 件 基 础 一. 哈希表的概念及建立 1. 哈希表的有关概念 （1）哈希函数 哈希函数是指对于线性表中各个元素所建 立的关键字值与其在一维数组中存放位置之 间的函数（对应关系），其形式为： addr(ai ) = H(ki ) 其中，H为哈希函数名，ai为线性表中的 第i个元素，ki为第i个元素的关键字值
2爱裂 (2)哈希地址 通过哈希函数,对线性表中的每个元素根 |据其关键字值所计算出的在一维数组中的存 放位置称为该元素的哈希地址。 (3)哈希表 按哈希地址存放每个元素所生成的顺序表 称作哈希表。哈希表空间的单元数应大于元 素的个数
计 算 机 软 件 基 础 （2）哈希地址 通过哈希函数，对线性表中的每个元素根 据其关键字值所计算出的在一维数组中的存 放位置称为该元素的哈希地址。 （3）哈希表 按哈希地址存放每个元素所生成的顺序表 称作哈希表。哈希表空间的单元数应大于元 素的个数
石 86,34,12,77},对其构造的哈希函数为: H(k)=k/10,若所开辟的哈希表空间地址范 算围为0-9,则形成的哈希表如下所示: 软地址0123456789 关键 12 3447 657786 字值 思考:若还存在关键字为69的元素,在 生成哈希表的过程中会有什么麻烦,有什么办 法能解决?
计 算 机 软 件 基 础 例：若有一线性表的关键字集合为{65，47， 86，34，12，77}，对其构造的哈希函数为： H(k) = k/10，若所开辟的哈希表空间地址范 围为0—9，则形成的哈希表如下所示： 地址 0 1 2 3 4 5 6 7 8 9 关键 字值 12 34 47 65 77 86 思考：若还存在关键字为69的元素，在 生成哈希表的过程中会有什么麻烦，有什么办 法能解决？
2 在计算哈希地址时所出现的不同关键字 算对应到同一地址的现象,称为冲突 处理冲突中的两个关键问题: 基|1如何构造合适的哈希函数以使冲突降低到 最少程度; 2.是如何在冲突出现时正确地处理冲突
计 算 机 软 件 基 础 （4）冲突 在计算哈希地址时所出现的不同关键字 对应到同一地址的现象，称为冲突。 ❖ 处理冲突中的两个关键问题： 1. 如何构造合适的哈希函数以使冲突降低到 最少程度； 2. 是如何在冲突出现时正确地处理冲突
恰希函数的构造方法 (1)直接定址法 取关键字值本身或其线性函数值作为哈 算机软件基础 希地址。其形式为:H(k)=a×k+b,其中a和 b为常数。 (2)数字分析法 取关键字中分布较均匀的n个数位作为哈 希地址(n的值应为哈希表的地址位数)
计 算 机 软 件 基 础 2．哈希函数的构造方法 （1）直接定址法 取关键字值本身或其线性函数值作为哈 希地址。其形式为：H(k) = a×k+b，其中a和 b为常数。 （2）数字分析法 取关键字中分布较均匀的n个数位作为哈 希地址（n的值应为哈希表的地址位数 ）
2爱裂 (3)平方取中法 取关键字平方后的中间几位作为哈希 算地址,是对数字分析法的改进方法 (4)除留余数法 取关键字被某个不大于哈希表表长m的 础数p除后所得的余数作为哈希地址,其形式 为:H(k)=k%p。一般情况下,可以选p 为不大于m的最大质数
计 算 机 软 件 基 础 （3）平方取中法 取关键字平方后的中间几位作为哈希 地址，是对数字分析法的改进方法。 （4）除留余数法 取关键字被某个不大于哈希表表长m的 数p除后所得的余数作为哈希地址，其形式 为：H(k) = k % p。一般情况下，可以选p 为不大于m的最大质数
冲突的处理方法 1.开放定址法 基本思想:若在某个地址处发生了冲突,则 算沿着一个特定的探测序列在哈希表中探测下 个空单元,一旦找到,则将新元素存入此 单元中。其探测的序列可用下式描述: H1=(H(k)+di)%m(i=1,2,3, 。 (1)当d取1,2,3,…,m-1时,称为线性 探测再散列; (2)当d取12,-12,22,-22,32,-32,…, 士2(jm/2)时,称为二次探测再散列
计 算 机 软 件 基 础 二. 冲突的处理方法 1． 开放定址法 基本思想：若在某个地址处发生了冲突，则 沿着一个特定的探测序列在哈希表中探测下 一个空单元，一旦找到，则将新元素存入此 单元中。其探测的序列可用下式描述： Hi = ( H(k) + di ) % m （i = 1，2，3，… ) （1）当di取1，2，3，…,m –1时，称为线性 探测再散列； （2）当di取1 2 ，–1 2 ，2 2 ，–2 2 ， 3 2 ，–3 2 ，…， ±j 2（j≤m/2）时，称为二次探测再散列
2爱裂 2.链地址法 基本思想:为每个哈希地址建立一个单链表, 算将所有哈希地址相同的元素存储在同一单链 表中,单链表的头指针存放在基本表中。在 将某个关键字的结点向单链表中插入时,既 础|可以插在链尾上,也可以插在链头上
计 算 机 软 件 基 础 2． 链地址法 基本思想：为每个哈希地址建立一个单链表， 将所有哈希地址相同的元素存储在同一单链 表中，单链表的头指针存放在基本表中。在 将某个关键字的结点向单链表中插入时，既 可以插在链尾上，也可以插在链头上
额产强 21,78,66,32,54,48),现用除留余 话数法作为哈希函数,分别用①线性探测再散 算机软件基础 列、②二次探测再散列处理冲突、③链地址 法处理冲突,画出所生成的哈希表。 关键62301845217866325448 字 地址7871101010104 哈希地址表
计 算 机 软 件 基 础 ❖ 例：设有关键字序列（62，30，18，45， 21，78，66，32，54，48），现用除留余 数法作为哈希函数，分别用①线性探测再散 列、②二次探测再散列处理冲突、③链地址 法处理冲突，画出所生成的哈希表 。 关键 字 62 30 18 45 21 78 66 32 54 48 地址 7 8 7 1 10 1 0 10 10 4 哈希地址表