牛小飞《数据结构》5散列表.pptx

散列表散列函数的构造方法处理冲;已讲查找表的共同特点：记录在表;用这类方法表示的查找表，其平均;只要记录在表中位置和其关键字之;例如：为每年招收的1000名新;散列的基本思想因此在一般情况下;设散列函数f(key)=;字母ABCDEFGHIJKLM;01散列(Hash)函数是一个;21很难找到一个不产生冲突的散;根据设定的散列函数H(key;除留余数法折叠法随机数法数字分;散列函数为关键字的线性函数H(;02此方法仅适合于：能预先估计;散列函数的构造方法有80个记录;关键字中的每一位都有某些数字重;折叠法01将关键字分割成若干部;散列函数的构造方法例关键;散列函数的构造方法5.除留余;给定一组关键字为:12,3;随机数法设定散列函数为:H(k;01采用哪种构造散列函数的方法;处理冲突的方法冲突：由关键字得;01分离链接法(separat;处理冲突的方法1例如:关键字;处理冲突的方法1执行一次查找：;处理冲突的方法1执行插入操作：;为产生冲突的地址H(key);01平方探测再散列法02双散列;开放定址法线性探测再散列di;处理冲突的方法2例如:关键字;di=f(i)=12,-;处理冲突的方法2例如:关键字;di即f(i)是一组随机数列;1H2(key)是另设定的一;处理冲突的方法例如，当m=1;壹即：产生的Hi均不相同，;Hi=RHi(key)i=;散列函数的值域[0,m-1]0;课堂练习设有一组关键字{11，r[i];从查找过程得知：哈希表查找的平;选用的哈希函数;选用的处理冲突;哈希表的查找分析一般情况下，可;随机探测再散列01链地址法02;从以上结果可见，01哈希表的平;小结和作业散列表1．散列原理