哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　126Computer CD Software and Applicationsspecial focus本期关注两化融合本章将简要的讨论哈希函数查找算法问题，先简单描述常用六种构造哈希函数的算法，然后选取开放定址法，再哈希法和链地址法来对其算法思想进行介绍，最后再结合实际的例子来比较分析说明哈希函数各构造方法的查找效率。1 哈希函数查找算法简述直接定址法算法思想：首先构造一线性哈希函数H（key）=key或H（key）=a*key+b，然后根据该函数来进行查找。若构造时采用H（key）=a*key+b函数，这时候选择常数a和b就显得比较重要了，这可以结合表长m来考虑，一般情况下凭经验也可以做到这一点。数字分析法算法描述思...

　　126Computer CD Software and Applicationsspecial focus本期关注两化融合本章将简要的讨论哈希函数查找算法问题，先简单描述常用六种构造哈希函数的算法，然后选取开放定址法，再哈希法和链地址法来对其算法思想进行介绍，最后再结合实际的例子来比较分析说明哈希函数各构造方法的查找效率。1 哈希函数查找算法简述直接定址法算法思想：首先构造一线性哈希函数H（key）=key或H（key）=a*key+b，然后根据该函数来进行查找。若构造时采用H（key）=a*key+b函数，这时候选择常数a和b就显得比较重要了，这可以结合表长m来考虑，一般情况下凭经验也可以做到这一点。数字分析法算法描述思想：首先从整体上分析所得到的关键字序列，考虑是选用二进制，八进制，十六进制或十进制等类型中的一种作为基数r，然后对关键字序列的各数字的数位字进行分析，最后以重新组合的若干数位作为哈希地址来进行查询。平方取中法算法思想：首先对各关键字序列进行平方，然后考虑对关键字进行取中操作。取中时，可以结合给定的哈希表长m来考虑，一般情况下是按照2^nm这样一种方式来选取，如果不满足这一点，按照我们自己选定的长度来取也可以，接着就可以依此法进行查找了。折叠法算法思想：首先整体分析所得到的关键字，然后将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址来进行查找。若关键字较多，并且各关键字在同一数位上的数字分布较均匀时，选用此法是可行的。除留余数法算法思想：首先选取一不大于哈希表表长m的质数p，然后用它来对关键字进行求模运算，最后用所得的余数作为所需要的哈希地址进行查找即可。随机数法算法思想：首先选择一随机函数random（x），然后利用它来构造哈希函数H（key）=random（key）。鉴于此法具有随机性，因此通常用于关键字长度不等的情况。介绍完常用六种构造哈希函数的基本方法后，为处理◆中图分类号：TP309哈希函数构造方法研究杜志林 / 北京师范大学珠海分校摘 要：在利用计算机对大量散列信息进行处理时，人们发现通过构造哈希函数对信息进行存储和查询是一种行之有效的方法。但是，人们在处理这类问题的过程中发现该函数还存在着一个主要的问题，就是在由关键字到地址的映射时发生了“冲突”，即出现了多个关键字对应一个地址，与我们想要得到的一个关键字只对应一个地址的设想出现了偏差。尽管在这方面有许多专家学者从事过研究，但依然未能很好的解决这种“冲突”。因此，为了更好地解决该问题，应尽量选择一种更合理的构造哈希函数的方法来解决这种“冲突”，达到评价哈希函数所要满足的好坏标准“使函数值尽可能均匀的分布到散列地址空间中，减少冲突发生的次数”的要求，实现对信息的高效存储或查找。本文正是基于这一目的，对前人的算法进行分析比较、给出实例验证。在前人算法的基础上做了一些改进，减少了冲突发生的次数。关键词：散列；哈希函数；冲突冲突的必要，下面介绍三种比较常用的哈希冲突处理算法的思想。开放定址法算法思想：首先指定表长m和增量序列di，然后构造散列函数 Hi=（H（key）+di）MOD m，i=1，2，，k（k=m-1）。在检索过程中，如果增量di取自然增量1，2，，m-1时，则此时散列函数Hi呈线性变化，存储的关键字位置也呈线性变化；如果增量di取k*k或-k*k（即k，kN）时，则此时散列函数呈波动的状态，存储的关键字地址也就相应地呈现波动的状态；如果增量di 取伪随机数序列，则此时的关键字的存储位置随该增量的随机变化而变化。找到相应的关键字后，就可以发现所需要的信息了。若查找完毕没有发现所要查找的关键字，则说明所要查找的信息根本就不存在。再哈希法算法思想：先考察哈希函数的构造方法，针对不同的方法，然后在查找的过程中采用与之相类似的不同再哈希函数一直哈希到不再产生冲突时为止，这样便完成了一次查找。依此类推，直到查找出所有需要的关键字，找出对应的信息，查找成功；或是查找完毕，找不到所需要的信息，查找失败。链地址法算法思想：先构造一定长的静态地址表（可以为数组），然后结合所选用的哈希函数找出关键字对应的地址。如发现在关键字到地址的映射过程中出现了同义词冲突，则按照关键字递增顺序将其构成一单链表，链接到发生冲突时的那个地址上即可。接下来就可以顺着链表往下查找，直到找出我们所需要的信息，查找成功；或是查找完毕，找不到所需要的信息，查找失败。当然哈希函数的查找算法远不只以上几种，但这几种是比较常见的，下面将结合一个实际的例子来比较说明哈希函数的这几种构造方法的查找效率。2 实例分析实例：现给定一组已经存储了的信息，用一结构体数组来存储，即：Search s[20]={{0，1}，{1，1}，{2，1}，{3，1}，计算机光盘软件与应用5期内页-出版d 1262014-4-16 12:04:40