济南大学信息科学与工程学院数据结构课件 第七章.ppt

折半有哪些信誉好的足球投注网站的特点：多数情况下折半有哪些信誉好的足球投注网站的效率比顺序有哪些信誉好的足球投注网站高但它只适用于有序表，而且只适用于顺序存储结构。 折半查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。 将关键字序列（7、8、30,11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数 ：H（key）=（key×3）MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7 问题： （1）请画出所构造的散列表； （2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 查找某一条记录需要进行一系列的“比较”。 查找的效率依赖于比较的次数。 能否在记录的关键字和存储地址之间构造这样一种关系 f ，使得关键字和存储地址一一对应 ？ 这种对应关系 f 称为散列函数（哈希函数）。 前面介绍的内容中 200302 200305 200301 张三 李四 王五 19 21 20 学号 姓名 年龄 01 02 03 §6.5 散 列 在散列方法中所用转换函数叫做散列函数(哈希函数)。 按此方法构造出来的表叫做散列表(哈希表)。 通过散列函数建立了从元素关键码集合到散列表地址 集合的一个映射，有了散列函数就可以根据关键码， 确定元素在散列表中唯一的存放地址 使用散列方法进行有哪些信誉好的足球投注网站不必进行多次关键码的比较, 有哪些信誉好的足球投注网站速度比较快, 可以直接到达或逼近具有此关键码 的表项的实际存放地址。 散 列的特点 例 30个地区的各民族人口统计表 编号 地区别 总人口 汉族 回族…... 1 北京 2 上海 …... …... 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2 以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 散列表(哈希表) 一般情况下，冲突只能尽量减少，而不能完全避免， 对于散列方法, 需要讨论以下两个问题： (1) 对于给定的关键码集合，选择一个计算简单且 地址分布比较均匀的散列函数，尽量减少冲突； (2) 冲突发生后，拟订解决冲突的方案。 哈希表 从例子可见： 哈希函数是一种压缩映象函数 ，键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算， 把不同的关键码映射到同一个散列地址上，就会产生哈希冲突。 冲突：key1?key2，但H(key1)=H(key2)的现象叫冲突。 同义词：具有相同函数值的两个关键字，叫该哈希函数的同义词。 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。 §6.5 散 列 散列函数的构造方法 构造散列函数的要求： 散列函数应是简单的，能在较短的时间内计算出 结果。 散列函数的定义域必须包括需要存储的全部关键码， 如果散列表允许有 m 个地址时，其值域必须在 0 到m-1 之间。 散列函数计算出的地址应能均匀的分布在整个地址 空间中：若 key 是从关键码集合中随机抽取的一个 关键码，散列函数应能以同等概率取0 到 m-1 中的 每一个值。 哈希函数的构造方法 1 直接定址法 取关键字或关键字的某个线性函数值为哈希地址。 H(key) = key (i) 或 H ( key) = a key + b . (ii) (i) 例，以年龄作为关键字 (ii) 例，统计解放后出生人口，以出生年份作为关键字 地址 出生年份 01 1949 02 1950 23 1971 48 1996 . . . . . . . . . . . . . . . . . . H(key) = key – 1949 + 1 这类散列函数是一对一的映射，一般不会产生冲突。 但它要求散列地址空间的大小与关键码集合的大小相同。 2 除留余数法 Hash (key) = key % p p ? m 例:关键字 28 33 69 64 107 p = 7 哈希地址 0 5 6 1 2 p的选择非常重要,否则容易产生冲突 设散列表中允许地址数为m，取一个不大于 m，但最接近于或等于 m 的质数 p 作为除数，用以下函数把关键码转换成散列地址：