《数据结构-C语言描述》课件第8章.ppt

＃definem哈希表长度＃defineNULLKEY代表空记录的关键字值typedefintKeyType;typedefstruct{KeyTypekey;…}RecordType;typedefRecordTypeHashTable［m］;intHashSearch(HashTableht,KeyTypeK){p0=hash(K);if(ht［p0］.key==NULLKEY)return(-1);elseif(ht［p0］.key==K)return(p0);else/*用线性探测再散列解决冲突*/{for(i=1;i=m-1;i++){pi=(p0+i)%m;if(ht［pi］.key==NULLKEY)return(-1);elseif(ht［pi］.key==K)return(pi);}return(-1);}}【算法8.15哈希表的查找算法】8.4.4哈希法性能分析由于冲突的存在，哈希法仍需进行关键字比较，因此仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个：哈希函数、处理冲突的方法以及哈希表的装填因子。哈希表的装填因子α的定义如下：α=哈希表中元素个数哈希表的长度α可描述哈希表的装满程度。显然，α越小，发生冲突的可能性越小，而α越大，发生冲突的可能性也越大。假定哈希函数是均匀的，则影响平均查找长度的因素只剩下两个：处理冲突的方法以及α。以下按处理冲突的不同方法分别列出相应的平均查找长度。■线性探测再散列查找成功时查找失败时■伪随机探测再散列、二次探测?查找成功时查找失败时■链址法查找成功时查找失败时从以上讨论可知：哈希表的平均查找长度是装填因子α的函数，而与待散列元素数目n无关。因此，论元素数目n有多大，都能通过调整α，使哈希表的平均查找长度较小。此外，我们还可以通过计算的方法得出用哈希法查找的平均查找长度。例如：已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）,按哈希函数H(key)=key%13和线性探测处理冲突构造所得哈希表ht［0..15］,如图8.28所示。图8.27哈希表ht［0..15］0123456789101112131415140168275519208479231110冲突计算次数(缺少部分为1次)②④③③⑨③查找19时，通过计算H（19）=6,ht［6］.key非空且值为19，则查找成功，因此查找关键字19，仅需要计算1次地址就可以找到。查找14时，通过计算H（14）=1,ht［1］.key非空且值为14，则查找成功，因此查找关键字14，仅需要计算1次地址就可以找到。查找23时，通过计算H（23）=10，ht［10］.key非空且值为23，则查找成功，因此查找关键字23，仅需要计算1次地址就可以找到。同样,查找关键字68，20，11，均需要计算1次地址就可以找到。查找关键字01时，通过计算H（01）=1，ht［1］.key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)%13=2,此时，ht［2］.key非空且值为01，查找成功，因此查找关键字01时，需要计算2次地址才可以找到。查找关键字55时，通过计算H（55）=3，ht［3］.key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)%13=