数据结构26-哈希表(一)

《数据结构26-哈希表(一)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第二十六课哈希表（一）第四十课哈希表（一）本课主题：哈希表（一）教学目的：掌握哈希表的概念作用及意义，哈希表的构造方法教学重点：哈希表的构造方法教学难点：哈希表的构造方法授课内容：一、哈希表的概念及作用1.散列函数的提出从前讲的检索，都是用待检索的关键字和各记录的关键字比较，若相等，则检索成功，否则，继续比较。我们希望找到一个函数，对关键字进行计算，把函数值解释为记录的存储地址，这就是散列检索。所用的函数就叫散列函数。用散列法存储的线性表叫散列表。查找时也用同样方法计算地址，到相应单元去找记录。若找到，则查找成功；若该单元无记录，则查找失败；若该单元有记录，但不是所找，要

2、继续查找。这种方法也称关键字-地址转换法。哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？最小值可能为3最大值可能为78可放75个学生用上述得到的数值作为对应记录在表中的位置，得到右表：上面这张表即哈希表。如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm12+17+13=42取表中第42条记录即可。问题：如果两个同学分别叫刘丽和刘兰该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得

3、到同一哈希地址。散列检索的术语根据设定的散列函数h(key)和处理冲突的方法，将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表称为散列表，这一映象过程叫散列（或哈希造表），所得存储地址称散列地址或哈希地址。碰撞（冲突）：两个关键字不同，但其散列函数值相同，即key1<>key2，f(key1)=f(key2)。冲突是不可避免的，举标识符的例子。1939年davenport的“生日悖论”。同义词：发生碰撞（冲突）的关键字称为同义词。负载因子：定义为=（散列表中结点的数目）/（散列表的长度）一般取0.6~0.9采用散

4、列表着重考虑两个问题：选择一个好的散列函数；选择一种解决碰撞（冲突）的方法。二、散列函数的构造方法１、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。２、数字分析法分析关键字的各位，去掉分布不均匀的位，留下均匀的位作为地址。有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15...经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。３、平方取中法关键字平方后取中间几位为哈希地址。４、折叠法

5、关键字位数较多，分布均匀，用折叠法。折叠法又分为移位折叠和间界折叠。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：５、除余法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=keyMODp(p<=m)６、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。7﹑基数转换法

6、将一个小基数的数看作大基数的数，再转换为小基数的数。如key=(215874)10,将其看作以13为基数，再转化为相应的十进制数。（215874）13=（783579）10，再进行数字分析，选2,3,4,5位，得h(215874)=8357。三、总结哈希表的优缺点回目录上一课下一课