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. 是如何在冲突出现时正确地处理冲突