赞
踩
散列存储:散列表,采用的存储方式是散列存储。那么何为散列存储呢?散列存储是根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。采用散列存储的方式存储数据时,具备的优点是在散列表中检索、增加和删除结点的操作很快;相反,它的缺点也相对比较明显,在插入结点的过程中,若散列函数选择不好,就可能在散列表中出现元素存储单元的冲突,解决冲突会额外的时间和空间开销,费时费力。
散列表:散列表是根据数据元素的关键字而直接进行访问的数据结构。通俗地讲,就是散列表建立了关键字和存储地址之间地一种直接映射关系。这种直接映射关系通过选择的散列函数来完成。
散列函数:散列函数又是什么呢?散列函数其实是一个把查找表中的关键字映射成该关键字对应的存储地址的函数,记为: Hash(key) = Adr(地址可以是数组下标、索引或内存地址等)。
冲突:何为冲突?冲突其实是通过选择的散列函数,对于两个或两个不同的关键字映射到同一个存储地址中。对于这些发生碰撞的不同关键字称为同义词。
如何解决冲突:解决冲突的发生有两个方面,一方面,是设计好的散列函数尽量去减少冲突的发生;另一方面,由于冲突不可避免,可以设计好处理冲突的方法。
理想状况下,散列表进行查找的时间复杂度为O(1),
在构造散列函数时,应该要注意以下几点:
(1)散列函数的定义域(存放关键字的存储单元)必须包含全部存储的关键字,而值域的范围则依赖于散列表的大小或地址范围。
(2)散列函数计算出来的地址是等概率的、均匀分布在整个地址空间中,减少冲突的发生。
(3)散列函数尽量简单,能够在较短时间内计算出任一个关键字的散列地址。
所谓开放定址法,是指可存放新表项的空间地址既向它的同义词开放,又向它的非同义词表项开放。其数学递推公式为:Hi = (H(key)+di)%m,式中,H(key) 为散列函数;i = 0,1,2,…,k(k<=m-1);m 表示 散列表表长;di为增量序列。通常有以下 4 种取法,分别是线性探测法、平方探测法、再散列法和伪随机序列法,简单介绍线性探测法和平方探测法。
线性探测法
当 di =0,1,2,…,m-1时,称为线性探测法。
特点:冲突发生时,顺序查看表中下一个单元(探测到表尾地址 m-1时,下一个探测地址是表首地址 0),直到找到一个空闲单元(当表未满时一定能找到一个空闲单元)或查遍全表。
缺点:线性探测法可能使第 i 个散列地址的同义词存入第 i+1 个散列地址,将本该存入第 i+1 个散列地址的元素就争夺第 i+2 个散列地址的元素地址,以此类推,从而照成大量元素在相邻的散列地址上“聚集”(或堆积)起来,大大降低了查找效率。
平方探测法(简单了解即可)
当 di = 0^2, 1^2, -1^2 , 2^2, -2^2,… ,k^2, -k^2 时,称为平方探测法,其中 k<=m/2,散列表长度 m 必须是一个可以表示成 4K+3 的素数,又称二次探测法。
特点:平方探测法是一种较好的处理冲突的方法,可以避免出现“堆积”问题。
缺点:不能探测到散列表上的所有单元,只能探测到散列表上的一半单元。
关键字序列{19,14,23,01,68,20,84,27,55,11,10,79}按散函数 H(key)=key%13 和线性探测法处理冲突所构造的散列表如下图所示。
该散列表是通过散列函数和线性探测处理冲突的方法得来的。例如19,通过19对13的余数可得余数为6,则19的散列地址为6,存入散列表中地址为6的存储单元;14除以13余数为1,存入1号地址;23除以13余数为10,存入 10号地址;01除以13余数为1,本来需要存入1号地址,但1号地址已经存入14,故向后探测一个存储单元,可见2号存储单元为空,存入其中即,同理可得上述散列表。
利用哈希函数和线性探测法处理冲突后,查找关键字得查找成功得平均查找长度和查找不成功得平均查找长度如下:
查找成功的平均查找长度
查找各关键字的比较次数如下图所示。
查找成功平均查找长度:
ASL(成功)=(1 * 6 +2 * 1+3 * 3+4+9)/12 =30/12=2.5
查找失败平均查找长度:
ASL=(13+12+11+10+9+8+7+6+5+4+3+2)/13=90/13
注意:对同一组关键字,设定相同的散列函数,不同的处理方法得到的散列表不同,它的平均查找长度也不同。散列表在查找过程中的时间复杂度为 O(1),平均查找长度 ASL=1,实际上由于冲突的存在,其ASL的值会比1大。
更多知识可点击博主主页进行查看,在这里你会学到很多知识,希望大家的支持和关注。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。