构造二叉排序树_二叉排序树的构造过程_二叉排序树怎么构造(3)

所在位置： 李秋梅:lqm 12+17+13=42 取表中第 42 条记录即可。 问题：如果两个同学分别叫刘丽 刘兰 该如何处理这两条记录？ 这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希 地址。 二、哈希表的构造方法 １、直接定址法例如：有一个从 1 到 100 岁的人口数字统计表，其中，年龄作为关键字，哈希函 数取关键字自身。 地址 年龄 人数 ... ２、数字分析法 有学生的生日数据如下： 年.月.日 75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 ... 经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增 加，所以尽量不取前三位，取后三位比较好。 ３、平方取中法 取关键字平方后的中间几位为哈希地址。 ４、折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几 部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。 例如：每一种西文图书都有一个国际标准图书编号，它是一个 10 位的十进制数 字，若要以它作关键字建立一个哈希表，当馆藏书种类不到 10,000 时，可采用 此法构造一个四位数的哈希函数。

如果一本书的编号为 0-442-20586-4,则： 5864 4220 +) 04 +) 5864 0224 04 01 1 3000 02 2 2000 ... ... ... 25 25 1050 26 26 ... 27 27 ... ... ... ... 100 ... ...----------10088 H(key)=0088----------6092 H(key)=6092(a)移位叠加 ５、除留余数法(b)间界叠加取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址。 H(key)=key MOD p (p<=m) ６、随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key)=random(key) ,其中 random 为随机函数。通常用于关键字长度不等时采 用此法。 三、总结 哈希表的优缺点 四、作业预习如何处理冲突及哈希表的查找。 回目录 上一课 下一课第三十三课：哈希表（ 第三十三课：哈希表（二）本课主题： 本课主题： 哈希表（二） 教学目的： 教学目的： 掌握哈希表处理冲突的方法及哈希表的查找算法 教学重点： 哈希表处理冲突的方法 教学重点： 教学难点： 教学难点： 开放定址法 授课内容： 授课内容：一、复习上次课内容 什么是哈希表？如何构造哈希表？ 提出问题：如何处理冲突？ 二、处理冲突的方法成绩一 成绩二... 3 ...... ... 24 25 26 刘丽 ... 陈伟 82 95... ... 33 吴军... ... 42 李秋梅... ... 46 刘宏英... ... 72 吴小艳... ... 78 ...如果两个同学分别叫刘丽 刘兰，当加入刘兰时，地址 24 发生了冲突，我们可以 以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下 一个，直到找到没有冲突的位置。选择其它位置的

方法有： １、开放定址法 Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1) 其中 m 为表长，di 为增量序列 如果 di 值可能为 1,2,3,...m-1，称线性探测再散列。 如果 di 取值可能为 1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2) 称二次探测再散列。 如果 di 取值可能为伪随机数列。称伪随机探测再散列。 例：在长度为 11 的哈希表中已填有关键字分别为 17,60,29 的记录，现有第四个 记录，其关键字为 38，由哈希函数得到地址为 5，若用线性探测再散列，如下：012345 606 17 (a)插入前7 298910012345 606 177 298 38910(b)线性探测再散列 0 1 2 3 4 5 60 6 17 7 29 8 9 10(c)二次探测再散列 0 1 2 3 38 4 5 60 6 17 7 29 8 9 10(d)伪随机探测再散列 伪随机数列为 9,5,3,8,1... ２、再哈希法 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-36021-3.html