资源描述：
《Hash表-构建方法-编程技巧》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、散列（Hashing)存贮假定键值均是正整数.散列存贮是通过对结点的键值做某种运算来确定具有该键值的结点的存放位置。设有线性表F=(k1,k2,…,kn-1)和数组T[m]，而结点ki的键值为Keyi，记F中所有结点的键值的集合为S.h(x)是从S到整数区间[0,m-1]上的一个一一对应函数。对于F中的任一结点Ki，都有一个h(keyi)的唯一值与之对应，Ki存放在数组T[m]中的位置就由h(keyi)决定。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyri
2、ght2004-2011AsposePtyLtd.这种存贮线性表F的方法，称为散列存贮。称函数h(x)为散列函数（HASH函数)。称存放结点的数组T(m)为散列表(Hash表).设F是含有六个结点的线性表，其中K0=(9,e),k1=(12,b),k2=(20,e),K3=(26,a),k4=(34,d),k5=(48,f).若取散列函数h(x)=xmod10，并使用能存放十个结点的数组T[10]作为Hash表，则下图表示了F的散列存贮的状况。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro
3、file5.2.0.0.Copyright2004-2011AsposePtyLtd.012345678920E12b34d26a48f9CEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.如果我们想找到key4=34的结点K4，那么只要计算出34mod10=4就能在数组元素T[4]中找到它。出现h(keyi)=h(keyj),称这种情况是冲突。散列存贮的两个主要问题是：一是选取散列函数；二是选取解决冲突的办
4、法。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.静态散列方法散列方法在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash()，使每个关键码与结构中一个唯一存储位置相对应：Address＝Hash(Rec.key)在搜索时,先对表项的关键码进行函数计算,把函数值当做表项的存储位置,在结构中按此位置取表项比较。若关键码相等,则搜索成功。在存放表项时,依相同函数计算存储位置,并按此位置存放。这种方法
5、就是散列方法。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.在散列方法中使用的转换函数叫做散列函数。按此方法构造出来的表或结构就叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较,搜索速度比较快,可以直接到达或逼近具有此关键码的表项的实际存放地址。散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。示例：有
6、一组表项，其关键码分别是12361,07251,03309,30976Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.采用的散列函数是hash(x)=x%73+13420其中，“%”是除法取余操作。则有：hash(12361)=hash(07250)=hash(03309)=hash(30976)=13444。就是说,对不同的关键码,通过散列函数的计算,得到了同一散列地址。我们称这些产生冲突的散列地址相同的
7、不同关键码为同义词。由于关键码集合比地址集合大得多,冲突很难避免。所以对于散列方法,需要讨论以下两个问题：Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.构造散列函数时的几点要求：散列函数应是简单的，能在较短的时间内计算出结果。散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许有m个地址时,其值域必须在0到m-1之间。散列函数对于给定的一个关键码集合,选择一个计算简单且地址分布比较均匀的散列函数,
8、避免或尽量减少冲突；拟订解决冲突的方案。Evalua
