Hash表_构建方法_编程方法.pptVIP

散列（Hashing)存贮;这种存贮线性表F的方法，称为散列存贮。称函数h(x)为散列函数（HASH函数)。 称存放结点的数组T(m)为散列表(Hash表). 设F是含有六个结点的线性表，其中K0=(9,e) ,k1=(12,b), k2=(20,e), K3=(26,a), k4=(34,d), k5=(48,f). 若取散列函数h(x)=x mod 10，并使用能存放十个结点的数组T[10]作为Hash表，则下图表示了F的散列存贮的状况。;0 1 2 3 4 5 6 7 8 9;如果我们想找到key4=34的结点K4，那么只要计算出 34 mod 10=4 就能在数组元素T[4]中找到它。 出现h(keyi)=h(keyj),称这种情况是冲突。 散列存贮的两个主要问题是：一是选取散列函数；二是选取解决冲突的办法。;静态散列方法; ; 采用的散列函数是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。 则有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是说, 对不同的关键码, 通过散列函数的计算, 得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为同义词。 由于关键码集合比地址集合大得多, 冲突很难避免。所以对于散列方法, 需要讨论以下两个问题： ;构造散列函数时的几点要求： 散列函数应是简单的，能在较短的时间内计 算出结果。 散列函数的定义域必须包括需要存储的全部 关键码, 如果散列表允许有 m 个地址时, 其 值域必须在 0 到 m-1 之间。 ;一、开式寻址法解决冲突;1.建立Hash表的插入运算。 为了把键值k存入Hash表，先计算出h(k)=i. 如果t[i] 是一个空位置（即t[i]=0),那么把k存入t[i],插入过程结束； 如果t[i]不是空位置（即t[i]≠0),那么再判断t[i]是否等于k， 若t[i]=k,则键值k已在Hash表中，插入过程结束； 否则，t[i]已被另一个键值所占用（发生冲突），此时必须为k找另一个空位置，最简单的办法是进行线性探测，我们可使用下面的循环探测地址序列：;(i+1) mod m (i+2) mod m …… (i+m-1) mod m 一旦找到一个空位置，就把k存入刚探测到的空位置上，插入过程结束； 如果用完整个探测地址序列还没有找到空位置，那么Hash表满，插入失败，过程结束。 例 Hash(x)=x%10; ;2.查找键值k 首先计算出h(k)=i. 如果t[i]=k,则查找成功，查找过程结束； 如果t[i]不等于k,那么必须按照上面所给出的循环探测地址序列进行查找。 查找过程一直进行到下面三种情况之一出现为止： （1）当前位置上的键值等于k，则查找成功。 （2）找到一个空位置，则查找失败。 （3）用完循环探测地址序列还没有找到k,则查找失败。;3.删除键值K. 首先在Hash表t[m]上进行查找。 如果查找成功，假定t[j]=k,那么应把t[j]删除。但是，我们不能把t[j]置成空，而只能标上已被删除的标记，否则将会影响以后的查找。因此，在插入时，凡遇到标有删除标记的位置都可以插入；而在查找时，凡遇到标有删除标记的位置，还要继续查下去。; 实现上面各种运算的程序。 我们假定所使用的键值是大于零的整数，用0对Hash表t[M]进行初始化，用－1作为删除标记，所使用的Hash函数是h(x). ;#define M 100 void makenull(t) int t[ ]; {int i; for(i=0;im;i++)t[i]=0; } ;int insert1(t,k) int t[ ],k; {int i,j; i=h(k); for(j=0;jm t[(i+j)%M]!=kt[(i+j)%M]0;j++); i=(i+j)%M; if (t[i]=0) {t[i]=k; return(0); } return(1); }; ; ; ;int search1(t, k) int t[ ],k; {int i ,j; i =h(k); for(j=0;jmt[(i+j)%M]!=kt[(i+j)%M]!=0; j++); i=(i+j)%M; if(t[i]==k)return(i); return(-1); }; ;int deletel(t,k) int t[ ],k; {int i,j; i=h(k); for(j=0;jm t[(i+j)%M]!=kt[(i+j)%M]!=0;j++); i=(i+j)%M; if(t[i]==k) {t[