无限网状结构对拉链法解决地址冲突问题的优化无线互联科技
作者：计算机核心期刊投稿 人气：158 来源： 标签：无线互联科技论文发表
散列表．又称为哈希表，是线性表中一种重要的存储方式和检索方法。在散列表中，可以对节点进行快速检索。散列表算法的基本思想是：由结点的关键码值决定结点的存储地址，即以关键码值k为自变量，通过一定的函数关系h(称为散列函数)，计算出对应的函数值h(k)来，将这个值解释为结点的存储地址，将结点存入该地址中，检索时，根据要检索的关键码值，用同样的散列函数计算出地址，然后，到相应的地址中去获取所要的结点数据。因此，散列表有一个重要特征：平均检索的长度不直接依赖于表中元素的个数。两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。拉链法是解决冲突问题的传统方法，可拉链法存在一些缺点，用无限网状结构可以解决部分问题。
2拉链法解决地址冲突问题
拉链法解决地址冲突问题的基本思想：将所有关键字为同义词的结点放在同一个连表中。若选择的链表长度为m,则可将散列表定义为一由m个头指针组成的指针数组T[0...m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中个分量的初值均为空指针。
例1：已知一组数据为（26,36,41,38,44,15,68,12,06,51,06,51,），用除余法构造散列函数，用线性探测法解决冲突构造这组关键字的散列表
为了减少冲突通常令装载因子小于1，这里关键字个数n=10，不妨设计m=13,此时装载因子为0.77，散列表为T[0.....12],散列函数为：h(key)=key%13。由除余法的散列函数计算出的上述关键字的地址为（0,10,2,12,5,2,3,12,6,12），前五个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10]，T[2]，T[12]和T[5]中，当插入第六个关键字15时，其散列地址为2已被关键字41占用。故用拉链法存储15，即重新申请一个空间将15放入空间中，对12和51处理方法是一样的
图1拉链法结构图
拉链法的缺点：单链表对于同义词的存储没有采用合适的算法解决，即使在单链表中采用了很好的算法解决存储问题，但是若是在单链表中又出现冲突时问题无法解决。
3无限网状结构解决地址冲突问题
无限网状结构解决地址冲突问题的基本思想：将关键字放在带头指针的数组，数组数目可以视数据量自行申请空间设置，但是所有数组结构都是一样的。若选择的数组的长度为m,则可将数组定义为一由m个头指针组成的指针数组T[0...m-1]，然后各各数组之间的相互连接方式，根据实际情况自行进行，所有数组中关键字的存储都按照相应的散列函数来确定其在相应数组中的位置。
例2：已知一组英文单词：zero about out great hight konw home void play int floay fabt faat fbet将这些关键字存入散列表中。
本例中我们用无限网状结构来存储，将关键字的值减去a的值作为其地址，不同数组散列函数不同，并且每一个备份空间，一次用其下一个字符来确定其地址，由题可知about floay great hight int know out play void zero的地址分别是0 5 6 7 8 10 14 15 21和25，但是home faat fabt fbet他们出现了地址冲突，必须进行处理，对home开创一个数组将其按照第二个字母确定其地址，对于 fabt fbet必须创建一个数组进行储存，又因为faat和fabt关键字的发生了冲突，故应该在此运用拉链法来解决，即在申请一个数组空间来存储该关键字，这些关键字的存储结果结构图如下图：
图2无限网状结构的机构图
拉链法和无限网状结构的联系：无限网状结构是对拉链法的优化，它是将用拉链法解决冲突的散列表退化成一个数组，即无限网状结构的一个元素，然后根据实际情况自行连接各各元素，即拉链法的反复应用。无限网状结构就是将拉链法反复的应用在一个散列表中，很好的解决散列表中的地址冲突问题，既能够很好的解决对于同义词在备份空间的存储方法问题，又能很好的解决在同义词中又出现地址冲突问题，弥补了拉链法既解决不了同义词的存储方法问题又解决不了同义词中出现地址冲突问题，完善了拉链法，是对拉链法的充分应用。
[1]
·上一篇：从佛光寺东大殿的恢弘结构中考究唐代建筑艺术风格
·下一篇： 传媒公共话语空间的新思考文章来自魅力中国杂志论文发表
