《浅谈hash》PPT课件

《《浅谈hash》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈希表现在要储存和使用下面的线性表：A:(1,75,324,43,1353,90,46).我们可以定义一维数组a:array[1..n]oflongint;我们需要用O(n)的时间来查找某个元素也可以定义a:array[1..1353]oflongint使a[key]:=key;也就是我们所学过的桶排序；这样时间效率会变成O(1)一次查找VS多次查找（找K次）O(K*n)O(K)桶排的弊端A:(18,75,60,43,54,90,46)h[i]:=imod13012345678910111218mod13=575mod13=1060mod13=843mod13=454mo

2、d13=290mod13=1246mod13=7基本原理—使用一个下标范围比较大的数组a来存储元素，设计一个函数h，对于要存储的元素node，取一个关键字key，算出一个函数值h(key),把h(key)作为数组下标，用a[h(key)]存储node也可以简单理解为，按照关键字为每一个元素进行“分类”，然后将这个元素储存在相应的“类”所对应的地方A:(18,75,60,43,54,90,46,5,15,33)h[i]:=imod1301234567891011125443184660759018mod13=575mod13=1060mod13=843mod13=454mo

3、d13=290mod13=1246mod13=75mod13=515mod13=231mod13=5哈希表、哈希函数、冲突如何解决冲突，下面再说构造函数的常用方法（下面为了叙述简洁，设h(k)表示关键字为k的元素所对应的函数值）：A:(18,75,60,43,54,90,46)C=2(负的也可以)m[20]:=18m[77]:=75m[62]:=60m[45]:=43m[56]:=54m[92]:=90m[48]:=46C=0时1、直接定址法以关键字Key本身或关键字加上某个数值常量C作为散列地址的方法。散列函数为：h(Key)=Key+C，若C为0，则散列地址就是关键字

4、本身。2、除余法选择一个适当的正整数m，用m去除关键码，取其余数作为地址，即：h(Key)=Keymodm，这个方法应用的最多，其关键是m的选取,一般选m为小于某个区域长度n的最大素数（如例1中取m=13），为什么呢？就是为了尽力避免冲突。假设取m=1000，则哈希函数分类的标准实际上就变成了按照关键字末三位数分类，这样最多1000类，冲突会很多。一般地说，如果m的约数越多，那么冲突的几率就越大。简单的证明：假设m是一个有较多约数的数，同时在数据中存在q满足gcd(m,q)=d>1，即有m=a*d,q=b*d,则有以下等式：qmodm=q–m*[qdivm]=q–m*[b

5、diva]。其中，[bdiva]的取值范围是不会超过[0，b]的正整数。也就是说，[bdiva]的值只有b+1种可能，而m是一个预先确定的数。因此上式的值就只有b+1种可能了。这样，虽然mod运算之后的余数仍然在[0，m-1]内，但是它的取值仅限于等式可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出，m的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手”3、数字分析法常有这样的情况：关键码的位数比存储区域的地址的位数多，在这种情况下可以对关键码的各位进行分析，丢掉分布不均匀的位留

6、下分布均匀的位作为地址。本方法适用于所有关键字已知，并对关键字中每一位的取值分布情况作出了分析。【例2】对下列关键码集合（表中左边一列）进行关键码到地址的转换，要求用三位地址。KeyH(Key)000319426326000718309709000629443643000758615715000919697997000310329329分析：关键码是9位的，地址是3位的，需要经过数字分析丢掉6位。丢掉哪6位呢？显然前3位是没有任何区分度，第5位1太多、第6位基本都是8和9、第7位都是3、4、5，这几位的区分度都不好，而相对来说，第4、8、9位分布比较均匀，所以留下这3位作

7、为地址（表中右边一列）。4、平方取中法将关键码的值平方，然后取中间的几位作为散列地址。具体取多少位视实际要求而定，取哪几位常常结合数字分析法。【例3】将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)，若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。5、折叠法如果关键码的位数比地址码的位数多，而且各位分布较均匀，不适于用数字分析法丢掉某些数位，那么可以考虑用折叠法。折叠法是将