第08章 哈希表.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,8,章 哈希表,数据结构,(C#,语言描述,),配套,PPT,北京大学出版社,制作：陈广 博客：,数据结构,(C#,语言描述,),配套,PPT,引入,数据结构,(C#,语言描述,),配套,PPT,在,C#,的万物之母,object,对象中定义了一个虚方法,GetHashCode(),，这个方法用于获取对象的哈希码。什么是哈希码？它有什么作用？为什么要在如此重要的类中定义这个方法？哈希码跟哈希表有什么内在的联系吗？本章将对这些问题展开论述。,8.1,概念引入,数据结构,(C#,语言描述,),配套,PPT,例,8-1 Demo8-1.cs】,使用学号查找学生地址,【,例,8-2 Demo8-2.cs】,哈希查找,地址,(Address),0,学号,(StuNum),索引,200809001,广西南宁,200809002,广西南宁,200809003,北京,200809004,上海,200809005,广东深圳,1,2,3,4,8.2,构造哈希函数的方法,数据结构,(C#,语言描述,),配套,PPT,构造哈希函数的目标是使哈希地址尽可能均匀地分布在连续的内存单元地址上，以减少冲突发生的可能性，同时使计算尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布不同，可构造出与之适应的各不相同的哈希函数。这里主要讨论几种常用的整数类型关键字的哈希函数构造方法。,8.2,构造哈希函数的方法,数据结构,(C#,语言描述,),配套,PPT,8.2.1,直接定址法,直接定址法取关键字或关键字的某个线性函数为哈希地址。即：,h(key)=key,或,h(key)=a*key+b,其中,a,、,b,为常数，调整,a,与,b,的值可以使哈希地址取值范围与存储空间范围一致。这种哈希函数计算简单，并且不会有冲突发生。它适合于关键字的分布基本连续的情况，若关键字分布不连续，将造成存储空间的大量浪费。,8.2,构造哈希函数的方法,数据结构,(C#,语言描述,),配套,PPT,8.2.2,数字分析法,该方法是提取关键字中随机性较好的数字位，然后把这些数位拼接起来作为哈希地址。它适合于所有关键字值都已知的情况，并需要对关键字中每位的取值分布情况进行分析。,位,6 1 3,1,7 6 3,2,6 2 3,2,6 8 7,5,6 2 3,4,3 6 3,4,6 2 7,0,6 6 1,6,6 1 7,7,4 6 3,8,6 1 3,8,1 2 6,1,6 1 3,9,4 2 2,0,提取结果,12,25,44,6,78,81,90,8.2,构造哈希函数的方法,数据结构,(C#,语言描述,),配套,PPT,8.2.3,除留余数法,除留余数法采用取模运算（,%,），把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址。哈希函数的形式为：,h(key)=key%p,除留余数法的关键是选好,p,，使得记录集合中的每个关键字通过该孩子数转换后映射到哈希表范围内任意地址上的概率相等，从而尽可能减少发生冲突的可能性。,507683,的二进制,1111011111100100011,507683%2,5,相当于取低,5,位二进制数,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。而发生冲突的可能性又跟以下两个因素有关：,装填因子,所采用的哈希函数,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示：,h,i,=(h(key)+d,i,)%m,其中,i=1,，,2,，,，,k(k m-1),其中,h(key),为哈希函数；,m,为哈希表长；,di,为增量的序列。根据,di,取值的不同，可以分成几种探测方法，,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,线性探测法,1,线性探测法的基本思想是：当发生冲突时，从冲突位置的下一个单元顺序寻找，只要找到一个空位，就把元素放入此空位中。顺序查找时，把哈希表看成一个循环表，即如果到最后一个位置也没有找到空位，则回到表头开始继续查找。此时，如果仍然未找到空位，则说明哈希表已满，需要进行溢出处理。,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1闭散列法（开放地址法）,线性探测法,1,已知一组关键字为（,12,，,19,，,23,，,28,，,39,，,51,，,56,，,76,，,84,），哈希表长,m=13,，哈希函数为：,h(key)=key%11,key,h(key),0,1,2,3,4,5,6,7,8,9,10,11,12,比较次数,插入,12,h(key)=12%11=1,12,1,1,插入,28,h(key)=28%11=6,28,6,1,19,8,1,插入,19,h(key)=19%11=8,插入,23,h(key)=23%11=1,23,1,2,插入,39,h(key)=39%11=6,39,6,2,插入,56,hkey)=56%11=1,56,1,3,插入,76,h(key)=76%11=10,76,10,1,插入,51,h(key)=51%11=7,51,7,3,插入,84,h(key)=84%11=7,84,7,5,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,线性探测法,1,每个元素经哈希函数计算出来的地址称为基地址，这种不同基地址的元素争夺同一个单元的现象叫做二次聚集。二次聚集实际上是在处理同义词之间的冲突时引发的非同义词的冲突。显然，这种现象对查找不利。线性探测很容易出现二次聚集，小的聚集能汇合成大的聚集，最终导致很长的探测序列从而降低哈希表的运算效率。,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,线性探测法的缺点是容易出现二次聚集，为了减少二次聚集的产生，可以加大探测序列的步长，使发生冲突的元素的位置比较分散。如果在地址,i,产生冲突，不是探测,i+1,地址，而是探测,i+1,2,，,i-1,2,，,i+2,2,，,i-1,2,，,的地址。该方法的优点是可以减少二聚集的产生，缺点是不易探测到整个哈希空间。,二次探测法,2,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,双重散列法,3,双重散列法又称二度哈希，是闭散列法中较好的一种方法，它是以关键字的另一个散列函数值作为增量。设两个哈希函数为：,h1,和,h2,，则得到的探测序列为：,(h,1,(key)+h,2,(key)%m,，,(h,1,(key)+2h,2,(key)%m,，,(h,1,(key)+3h,2,(key)%m,，,其中，,m,为哈希表长。由此可知，双重散列法探测下一个开放地址的公式为：,(h,1,(key)+i*h,2,(key)%m (1im-1),8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.1,闭散列法（开放地址法）,双重散列法,3,定义,h,2,的方法较多，但无采用什么方法都必须使,h,2,(key),的值和,m,互素才能使发生冲突的同义词地址均匀地分布在整个哈希表中，否则可能造成同义词地址的循环计算。若,m,为素数，则,h,2,取,1,至,m-1,之间的任何数均与,m,互素，因此可以简单地将,h,2,定义为：,h,2,(key)=key%(m-2)+1,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.2,开散列法（链地址法）,开散列法的常见形式形式是将所有关键字为同义词的结点链接在同一个单链表中。每个单链表中除了表头指针存储在哈希表数组中以外，所有元素都存储在数组以外的空间，哈希表没有“边界”，这也是“开散列法”名称的来源8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.2,开散列法（链地址法）,关键字为（,12,，,19,，,23,，,28,，,39,，,51,，,56,，,76,，,84,），哈希表长,m=13,，哈希函数为,h(key)=key%11,，如果使用开散列法进行存储，元素插入单链表时总是插在表头作为第一个结点。设插入顺序为（,12,，,28,，,19,，,23,，,39,，,56,，,76,，,51,，,84,），其结果将如图所示,0,1,2,3,4,5,6,7,8,9,10,11,12,56,23,12,39,28,84,51,19,76,8.3,哈希冲突解决方法,数据结构,(C#,语言描述,),配套,PPT,8.3.2,开散列法（链地址法）,与开放地址法相比，链地址法有如下优缺点。,优点：,使用链地址法处理冲突无二次聚集现象，因此平均查找长度较短。,由于链地址法中各链表上的结点空间是动态申请的，因此适合于无法确定表长的情况。,在用链地址法构造的哈希表中，删除结点的操作易于实现，只要删除链表上相应的结点即可。,缺点：,指针需要额外空间，故当记录规模较小时，闭散列法较为节省空间。,在,.NET,中，链表的各个元素分散于托管堆各处，这会给自动垃圾回收带来压力，影响程序性能。,8.4,剖析,System.Collections.Hashtable,数据结构,(C#,语言描述,),配套,PPT,C#,中实现了哈希表数据结构的集合类有：,System.Collections.Hashtable,System.Collections.Generic.Dictionary,前者为一般类型的哈希表，后者是泛型版本的哈希表。,Dictionary,和,Hashtable,之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。,8.4,剖析,System.Collections.Hashtable,数据结构,(C#,语言描述,),配套,PPT,object,类中定义了一个,GetHashCode(),方法，这个方法默认的实现是返回一个唯一的整数值以保证在,object,的生命期中不被修改。,GetHashCode(),方法使得,C#,中的所有类型都能以唯一的数字值来表示。,由于,GetHashCode(),方法是一个虚方法，可以通过重写这个方法来构造自己的哈希函数。,8.4,剖析,System.Collections.Hashtable,数据结构,(C#,语言描述,),配套,PPT,8.4.1,Hashtable,的实现原理,Hashtable,使用了闭散列法来解决冲突，它通过一个结构体,bucket,来表示哈希表中的单个元素，这个结构体中有三个成员：,key,：表示键，即哈希表中的关键字。,val,：表示值，即跟关键字所对应值。,hash_coll,：它是一个,int,类型，用于表示键所对应的哈希码。,8.4,剖析,System.Collections.Hashtable,数据结构,(C#,语言描述,),配套,PPT,8.4.1,Hashtable,的实现原理,Hashtable,解决冲突使用了双重散列法，但又跟前面所讲的双重散列法稍有不同。它探测地址的方式为：,h(key,i)=h,1,(key)+i*h,2,(key),其中哈希函数,h,1,和,h,2,的公式如下：,h,1,(key)=key.GetHashCode(),h,2,(key)=1+(h,1,(key)5)+1)%(hashsize-1),由于使用了二度哈希，最终的,h(key,i),的值有可能会大于,hashsize,，所以需要对,h(key,i),进行模运算，最终计算的哈希地址为：,哈希地址,=h(key,i)%hashsize,Hashtable,动态演示程序网址：,key.GetHashCode()%hashsize,Dictionary,内有两个数组：,一个数组名为,buckets,，用于存放由多个同义词组成的静态链表头指针；,另一个数组名为,entries,，它用于存放哈希表中的实际数据，同时这些数据通过,next,指针构成多个单链表。,8.5,剖析,Dictionary,数据结构,(C#,语言描述,),配套,PPT8.5.1,Dictionary,的实现原理,buckets,中所存放的是,Entry,结构体，它由四个部分组成：,key,：元素的键,value,：元素的值,hashCode,：元素的哈希码,next,：指向哈希表中下一个同义词的指针，实际为下一个同义词在数组中的索引，当不存在下一个同义词时，,next,的值为,-1,。,entries,buckets,0,1,2,3,4,5,6,0,1,2,3,4,5,6,hashCode,key,value,next,键,值,哈希码,指向下一个同义词的指针,Entry,结构体,8.5,剖析,Dictionary,数据结构,(C#,语言描述,),配套,PPT,8.5.1,Dictionary,的实现原理,为了正确添加和删除元素，,Dictionary,内部维护了三个成员变量：,count,freeCount,freeList,运行虚拟,Dictionary,8.6,本章小结,数据结构,(C#,语言描述,),配套,PPT,本章介绍了哈希表及,C#,中在现了哈希表的两个集合类,Hashtable,和,Dictionary,。两种哈希表的区别如下：,Hashtable,使用了闭散列法来解决冲突，而,Dictionary,使用了开散列法解决冲突。,Dictionary,相对,Hashtable,来说需要更多的存储空间，但它不会发生二次聚集的情况，并且由于使用泛型实现，,Dictonary,的速度更快些。,Hashtable,使用了填充因子的概念，,Dictionary,不存在填充因子的概念。,哈希表在扩容时由于需要重新计算哈希地址，会消耗大量时间进行计算，但,Dictonary,的扩容相对,Hashtable,来说更快些。,单线程程序中推荐使用,Dictionary,，多线程程序中推荐使用,Hashtable,。默认的,Hashtable,允许单线程写入，多线程读取，对,Hashtable,进一步调用,Synchronized(),方法可以获得完全线程安全的类型。而,Dictionary,非线程安全，必须人为使用,lock,语句进行保护，效率大为降低。,