恰希函数的构造方法 (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 哈希地址表