ch9散列结构及其应用ppt课件.ppt

《ch9散列结构及其应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、☞9.1集合的概念9.2集合的散列存储9.3散列表及其运算9.4散列结构下的查找性能分析9.5散列结构的应用——LZW压缩问题第9章散列结构及其应用集合:是具有相同属性的数据元素按任何次序排列而成。任一非空集合可表示为{a1,a2,…,ai,ai+1,…,an}，其中i为该元素的编号，是为了区别而任意标注的，不代表任何次序。☞集合中元素的个数称为集合的长度。当长度n＝0时，为空集。说明：☞集合中的元素可以按任何次序排列；☞集合的长度是可变化的，当向它插入一个元素后，其长度加1，从中删除一个元素，长度减1；☞集合中元素的数据类型相同，且可为任何一

2、种类型。9.1集合的概念☞9.2集合的散列存储9.3散列表及其运算9.4散列结构下的查找性能分析9.5散列结构的应用——LZW压缩问题第9章散列结构及其应用☞9.2.1散列的概念9.2.2散列函数的构造9.2.3处理冲突的方法9.2集合的散列存储散列（Hash）同顺序、链接和索引一样，是存储数据的又一种方法。散列存储的基本思想是：以所需存储的节点（数据元素）中的关键字(key)作为自变量，通过某种确定的函数H(称作散列函数或者哈希函数)进行计算，把求出的函数值作为该节点的存储地址，并将该节点或节点的关键字存储在这个地址中。散列存储中使用的函数H

3、(key)，称为散列函数或哈希函数。散列函数实现关键字到存储地址的映射（或称转换），H(key)的值称为散列地址或哈希地址。使用的数组空间或文件空间是数据进行散列存储的地址空间.这种存储结构被称为散列表或哈希表。例：假定一个集合为：{16,35,23,31,45,70}若规定每个元素key的存储地址H(key)＝key，(注：H(key)＝key称为散列函数)请画出存储结构图。解：根据散列函数H(key)＝key，可知元素16应当存入地址为16的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：地址…16…23…31…

4、35…45…70…内容312316354570散列存储下的插入与删除：在该存储方式下，若向集合中插入key=25的元素，可根据散列函数H(key)=key，计算出元素25的散列地址为25，即下标为25的存储单元。若在该集合中删除key=31的元素，同样可根据散列函数H(key)=key，计算出元素31的散列地址为31，即从下标为31的存储单元中取出该元素。冲突：上例讨论的散列表是一种理想的情况。实际应用中，常常出现一个待插元素的散列地址已被占用的情况，使得该元素无法直接存入到此单元中，我们称此现象为“冲突”。例如：若上例中的散列函数H(key)

5、为H(key)=key%10，则元素35和45的散列地址相同；当向散列表中插入元素45时，散列地址（下标为5的单元）已被占用，致使元素45无法存入到下标为5的单元中。冲突产生的原因：散列存储中，虽然冲突很难避免，但发生冲突的可能性却有大有小，这主要与三个因素有关。(1)与装填因子α有关α=哈希表中元素个数哈希表的长度α越小，冲突的可能性就越小；α越大(最大取1)时，冲突的可能性就越大。(2)与所采用的散列函数有关若散列函数选择得当，就能够使散列地址尽可能均匀分布在散列空间上，减少冲突的发生。(3)与解决冲突的方法有关方法选择的好坏也将减少或增加

6、发生冲突的可能性。9.2.1散列的概念☞9.2.2散列函数的构造9.2.3处理冲突的方法9.2集合的散列存储构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。常用的散列函数构造方法有：直接定址法除留余数法数字分析法平方取中法折叠法Hash(key)=a·key+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储

7、结构（哈希表）如下：01234567899008007005003001001、直接定址法Hash(key)=keymodp(p是一个整数)特点：以关键字除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数（也可以是不包含小于20质因子的合数）。2、除留余数法例：已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有H(18)=18%7=4H(75)=75%7=5H(60)=60%7=4H(43)=43%7=1H(54)=54%7=5H(90)=90%7=6H(

8、46)=46%7=4此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13。结果如下：H(18)=18%13=5H(75)=75%13=1