数据结构-哈希表

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

1、哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析小结和作业课堂练习A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]例1:有一批考试成绩，统计各分数段的人数。对成绩Grade，执行：A[grade/10]++什么是哈希表例2:Ord(Char)=asc(char)–asc(‘a’)+1什么是哈希表01(A)345(E)9(I)……268(H)4(D)19(S)22(V)018(R)7(G)1905(E)HADHASHAVHEHERHEREHIGHIS将1000个学生的信

2、息存放在数组A[0]—A[999]中例3:为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。什么是哈希表number(substring(学号,3,3))建立查找表：给定关键字key计算f(key)数组下标查找表：使用数组存放n个关键字，数组的下标0n-1什么是哈希表查找时：给定关键字key计算f(key)数组下标建立查找表：给定grade计算f(grade)数组下标例4：统计学生成绩各分数段的人数什么是哈希表查找时：给定grade计算f(grade)数组下标Hash函数：f(g

3、rade)=grade/10什么是哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例5：对于如下9个关键字设哈希函数f(key)=(Ord(第一个字母)-Ord('A')+1)/2什么是哈希表字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526ChenZhaoQianSunLiWuHanYeDei序号012345678910111213问题:若添加关键字Zhou,怎么办？什么是哈希表由此可见，1)哈希(Hash)函数是一

4、个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；2)对不同的关键字可能得到同一哈希地址，即：key1≠key2，而f(key1)=f(key2),因此，很容易产生“冲突”现象；什么是哈希表3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。哈希表的定义根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有

5、限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。这一过程称为哈希造表或者散列，所得的存储位置成为哈希地址或者散列地址。哈希函数的构造方法对数字的关键字可有下列构造方法:若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.直接定址法哈希函数的构造方法哈希函数的构造方法2.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(

6、u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。哈希函数的构造方法有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址哈希函数的构造方法以关键字的平方值的中间

7、几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。哈希函数的构造方法4.折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于:关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。哈希函数的构造方法例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加58640224046092H(k

8、ey)=6092间界叠加4.折叠法哈希函数的构造方法5.除留余数法