数据结构哈希表解析介绍资料.docx

《数据结构哈希表解析介绍资料.docx》由会员分享，可在线阅读，更多相关《数据结构哈希表解析介绍资料.docx（23页珍藏版）》请在优知文库上搜索。

1、在前面的系列文章中，依次介绍了基于无序列表的咽i查找，基于有序数组的二分查找,平衡查找树,以及红黑树,下图是他们在平均以及最差情况下的时间复杂改：Iimplementationworst-casecost(afterNinserts)average-casecost(afterNrandominserts)orderediteration?keyinterfacesearchinsertdeletesearchhitinsertdeletesequentialsearch(unorderedlist)NNNN/2NN/2noequals()binarysearch(orderedarray)I

2、gNNNIgNN/2N/2yesco11areTo()BSTNNN1.38IgN1.38IgN?yescoareTo()red-blackBST2IgN2IgN2IgN1.00IgN1.00IgN1.00IgNyescoareTo()可以看到在时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了IgN的时间复杂度。那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表(HaShTable)什么是哈希表哈希表就是一种以键-值(key-indexed)存储数据的结构，我们只要输入待查找的值即key,即可查找到其对应的值。哈希的思路很简单，如果所有的键都是整数，那么

3、就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。使用哈希查找有两个步骤：1 .使用哈希函数将被查找的键转换为数组的索引.在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突2 .处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为0(1)

4、;如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。哈希函数哈希查找第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果我们有一个保存0-M数组,那么我们就需要一个能够将任意键转换为该数组范围内的索引(O-MT)的哈希函数。哈希函数需要易于计算并且能够均匀分布所有键。比如举个简单的例子，使用手机号码后三位就比前三位作为key更好，因为前三位手机号码的重复率很高。再比如使用身份证号码出生年月位数要比使用前几位数要更好。在实际中，我们的键并不都是

5、数字，有可能是字符串，还有可能是几个值的组合等，所以我们需要实现自己的哈希函数。1 .正整数获取正整数哈希值最常用的方法是使用除留余数法。即对于大小为素数M的数组，对于任意正整数k,计算k除以M的余数。M一般取素数。2.字符串将字符串作为键的时候，我们也可以将他作为一个大的整数，采用保留除余法。我们可以将组成字符串的每一个字符取值然后进行哈希，比如publicintGetHashCode(stringstr)charts=str.ToCharArrayO；inthash=O;for(inti=O;is.Length;i+)(hash=si+(31*hash);)returnhash;)上面的哈

6、希值是HOrner计算字符串哈希值的方法，公式为：h=s031j+.+sL-33f+sL-231,+sL-131举个例子，比如要获取“Call”的哈希值，字符串C对应的UniCOde为99,a对应的UniCode为97,L对应的UniCode为108,所以字符串“call”的哈希值为3045982=993f+973l+10831+10831=108+31(108+31-(97+31-(99)如果对每个字符去哈希值可能会比较耗时，所以可以通过间隔取、个字符来获取哈西值来节省时间，比如，可以获取每8-9个字符来获取哈希值：publicintGetHashCode(stringstr)(chars=

7、str.ToCharArrayO;inthash=O;intskip=Math.Max(1,s.Length/8);for(inti=O;is.Length;i+=skip)hash=si+(31*hash);)returnhash;)但是，对于某些情况，不同的字符串会产生相同的哈希值，这就是前面说到的哈希冲突(HaShCollisions),比如下面的四个字符串：http:/www.cs.princeton.eduintrocs131oopHello.javahttp:/www.cs.princeton.eduintrocs131oopHello.classhttp:/wwwcsprince

8、ton.eduintrocs131oopHello.htmlhttp:/wwwcs.princeton.edu/introcs/12type/index.htmltTTTttTT如果我们按照每8个字符取哈希的话，就会得到一样的哈希值。所以下面来讲解如何解决哈希碰撞：避免哈希冲突拉链法(SeParateChainingWithlinkedlists)通过哈希函数，我们可以将键转换为数组的索引（0-M-D,但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。一种比较直接的办法就是，将大小为M的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，

9、这就是拉链法。下图很清楚的描述了什么是拉链法。keysbucketsentries151152153154Lisa Smithled Baker000001002 Sam Doe 521-5030521-8976253254255JOhnSmith 521-1234Sandra Dee 521-9655418-4165图中，JohnSmith和“SandraDec”通过哈希函数都指向了152这个索引，该索引又指向了一个链表，在链表中依次存储了这两个字符串。该方法的基本思想就是选择足够大的M,使得所有的链表都尽可能的短小，以保证查找的效率。对采用拉链法的哈希实现的查找分为两步，首先是根据散列值找

10、到等一应的链表，然后沿着链表顺序找到相应的键。我们现在使用我们之前介绍符号表中的使用无序链表实现的查找表SequontscarchSymbolTablc来实现我们这里的哈希表。当然,您也可以使用.NET里面内置的LinkListo首先我们需要定义,个链表的总数，在内部我们定义一个SeCIUentSearChSymbolTab表的数组。然后每个映射到索引的地方保存一个这样的数组。publicclassSeperateChainingHashSet:SymbolTableswhereTKey:IComparab1e,IEquatab1e(privateintM;散列表大小privateSequen

11、tSearchSymbolTablest;/publicSeperateChainingHashSet():this(997)publicSeperateChainingHashSet(intm)(this.M=m;st=newSequentSearchSymbolTablcm;for(inti=0;im;i+)(sti=newSequentSearchSymbolTableO;)privateinthash(TKeykey)(return(key.GetHashCode()&0x7fffffff)%M;)publicoverrideTValueGet(TKeykey)(returnsthas

12、h(key).Get(key);)publicoverridevoidPut(TKeykey,TValuevalue)(sthash(key).Put(key,value);可以看到，该实现中使用 Get方法来获取指定key的Value值，我们首先通过hash方法来找到key对应的索引值，即找到SequentSearchSymbolTab1e数组中存储该元素的查找表，然后调用查找表的Get方法，根据key找到对应的Valueo Put方法用来存储键值对，首先通过hash方法找到改key对应的哈希值,然后找到SequentSearchSymbolTable数组中存储该元素的查找表，然后调用查找表

13、的PUt方法，将键值对存储起来。 hash方法来计算key的哈希值，这里首先通过取与&操作，将符号位去除，然后采用除留余数法将key应到到0-MT的范围，这也是我们的查找表数组索引的范围。实现基于拉链表的散列表，目标是选择适当的数组大小M,使得既不会因为空链表而浪费内存空间，也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于，这种数组大小M的选择不是关键性的，如果存入的键多于预期，那么查找的时间只会比选择更大的数组稍长，另外，我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期，索然有些浪费空间，但是查找速度就会很快。所以当内存不紧张时，我们可以选择足够大的M,可以使得查找时间

14、变为常数，如果内存紧张时，选择尽量大的M仍能够将性能提高M倍。线性探测法线性探测法是五放辿解决哈希冲突的一种方法,基本原理为,使用大小为M的数组来保存N个键值对,其中MN,我们需要使用数组中的空位解决碰撞冲突。如下图所示：keysbuckets255Lisa Smith521-8976000John Smith521-1234Sandra Dee521-9655led Baker418-4165Sam Doe521-5030对照前面的拉链法,在该图中，TedBaker是有唯一的哈希值153的，但是由于153被SandraDee”占用了。而原先SnadraDee和JOhnSmilh”的哈希值都是152的，但是在对“SandraDee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以存放在153上，然后TedBaker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加L这样的线性探测会出现三种结果：1 .命中，该位置的键和被查找的键相同2 .未命中，键为空3 .继续查找，该位置和键被查找的键不同。实现线性探测法也很简单，我们只需要两