浅谈Hash

现在要储存和使用下面的线性表：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=454mod13=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=454mod13=290mod13=1246mod13=75mod13=515mod13=231mod13=5哈希表、哈希函数、冲突如何解决冲突，下面再说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，则散列地址就是关键字本身。2、除余法选择一个适当的正整数m，用m去除关键码，取其余数作为地址，即：h(Key)=Keymodm，这个方法应用的最多，其关键是m的选取,一般选m为小于某个区域长度n的最大素数（如例1中取m=13），为什么呢？就是为了尽力避免冲突。假设取m=1000，则哈希函数分类的标准实际上就变成了按照关键字末三位数分类，这样最多1000类，冲突会很多。一般地说，如果m的约数越多，那么冲突的几率就越大。简单的证明：假设m是一个有较多约数的数，同时在数据中存在q满足gcd(m,q)=d1，即有m=a*d,q=b*d,则有以下等式：qmodm=q–m*[qdivm]=q–m*[bdiva]。其中，[bdiva]的取值范围是不会超过[0，b]的正整数。也就是说，[bdiva]的值只有b+1种可能，而m是一个预先确定的数。因此上式的值就只有b+1种可能了。这样，虽然mod运算之后的余数仍然在[0，m-1]内，但是它的取值仅限于等式可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出，m的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手”3、数字分析法常有这样的情况：关键码的位数比存储区域的地址的位数多，在这种情况下可以对关键码的各位进行分析，丢掉分布不均匀的位留下分布均匀的位作为地址。本方法适用于所有关键字已知，并对关键字中每一位的取值分布情况作出了分析。【例2】对下列关键码集合（表中左边一列）进行关键码到地址的转换，要求用三位地址。KeyH(Key)000319426326000718309709000629443643000758615715000919697997000310329329分析：关键码是9位的，地址是3位的，需要经过数字分析丢掉6位。丢掉哪6位呢？显然前3位是没有任何区分度，第5位1太多、第6位基本都是8和9、第7位都是3、4、5，这几位的区分度都不好，而相对来说，第4、8、9位分布比较均匀，所以留下这3位作为地址（表中右边一列）。4、平方取中法将关键码的值平方，然后取中间的几位作为散列地址。具体取多少位视实际要求而定，取哪几位常常结合数字分析法。【例3】将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)，若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。5、折叠法如果关键码的位数比地址码的位数多，而且各位分布较均匀，不适于用数字分析法丢掉某些数位，那么可以考虑用折叠法。折叠法是将关键码从某些地方断开，分关键码为几个部分，其中有一部分的长度等于地址码的长度，然后将其余部分加到它的上面，如果最高位有进位，则把进位丢掉。一般是先将关键字分割成位数相同的几段（最后一段的位数可少一些），段的位数取决于散列地址的位数，由实际需要而定，然后将它们的对应位叠加和（舍去最高位进位）作为散列地址。【例4】如关键码Key=58422241，要求转换为3位的地址码。分析：分如下3段：584|222|41，则相加：58422241_______847h(Key)=8476、基数转换法将关键码值看成在另一个基数制上的表示，然后把它转换成原来基数制的数，再用数字分析法取其中的几位作为地址。一般取大于原来基数的数作转换的基数，并且两个基数要是互质的。如：key=(236075)10是以10为基数的十进制数，现在将它看成是以13为基数的十三进制数(236075)13,然后将它转换成十进制数。（236075）13=2*135+3*134+6*133+7*13+5=(841547)10再进行数字分析，比如选择第2,3,4,5位，于是h(236075)=4154A:(18,75,60,43,54,90,46,5)h(k)+c012345678910111254431846607590544318466075905A:(18,75,60,43,54,90,46,5)46901815754360515-1-111-1-1-1-1-1-1Record,keylinkr:=m哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。设插入的元素的关键字为x，A为存储的数组。初始化比较容易，例如constempty=maxlongint;//用非常大的整数代表这个位置没有存储元素p=9997;//表的大小proceduremakenull;vari:integer;beginfori:=0top-1doA[i]:=empty;End;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：functionh(x:longint):Integer;beginh:=xmodp;end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数locatefunctionlocate(x:longint):integer;varorig,i:integer;beginorig:=h(x);i:=0;while(iS)and(A[(orig+i)modS]x)and(A[(orig+i)modS]empty)doinc(i);locate:=(orig+i)modS;end;插入元素procedureinsert(x:longint);varposi:integer;beginposi:=locate(x);//定位函数的返回值ifA[posi]=emptythenA[posi]:=xelseerror;//error即为发生了错误，当然这是可以避免的end;查找元素是否已经在表中proceduremember(x:longint):boolean;varposi:integer;beginposi:=locate(x);ifA[posi]=xthenmember:=trueelsemember:=false;end;快排+二分：O(n)=n×log2n哈希表：O(n)=由于哈希函数的不同，时间复杂度很难估计下面来看一下两种排法的时间效率对比123456789101112但是，不能保证每个元素与函数值都是一一对应的，因此极有可能出现不同元素却出现了相同的函数值如15和28对于h(key):=keymod13有相同的函数值—2这样就产生了“冲突”另一个函数I现在要储存和使用下面的线性表：A:(1,75,324,43,1353,90,46).上述两种方法分别造成了时间和空间上的大量浪费，尤其是数据范围较广时，可以对第二种方法进行优化设计一个函数h(key):=keymod13然后把key储存在a[h(key)]中，这样的话定义一个0..12的数组就够了A:(18,75,60,43,54,90,46,5,15,33)h[i]:=imod1301234567891011125443184660759018mod13=575mod13=1060mod13=843mod13=454mod13=290mod13=1246mod13=75mod13=515mod13=231mod13=5