构造散列函数的目标是使散列地址尽可能均匀地分布在散列空间上.doc

构造散列函数的目标是使散列地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单，以节省计算时间根据关键字的结构和分布不同，可构造出与之适应的各不相同的散列函数，这里只介绍较常用的几种，其中又以介绍除留余数法为主在下面的讨论中，假定关键字均为整型数，若不是整型数则要设法把它转换为整型数后再进行运算1．直接定址法 直接定址法是以关键字 K 本身或关键字加上某个数值常量 C 作为散列地址的方法对应的散列函数 h(K)为：h(K)=K+C若 C 为 O，则散列地址就是关键字本身 这种方法计算最简单，并且没有冲突发生，若有冲突发生，则表明是关键字错误它适应于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将造成存储空间的浪费2．除留余数法除留余数法是用关键字 K 除以散列表长度 m 所得余数作为散列地址的方法对应的散列函数 h(K)为：h(K)=k％m 这种方法在上面的例中已经使用过除留余数法计算较简单，适用范围广，是一种最常使用的方法这种方法的关键是选好 m，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性例如，取 m 为奇数，比取 m 为偶数要好。

因为当 m 为偶数时，它总是把关键字为偶数的元素散列到偶数单元中，把关键字为奇数的元素散列到奇数单元中，即把_个元素只散列到一一半的存储空间中；当m 为奇数时就不会出现这种问题，它能够把一个元素散列到整个存储空间中结合处理冲突时对 m 的要求，最好取散列表的长度 m 为一个素数(即除 l 和本身之外，不能被任何数整除的数)当然，要确保 m 的值大于等于待散列的线性表的长度 n，根据装填因子 a 最好为在0．6至 O．9之间，所以 m 应取1．1n 至1.7n 之间的一个素数例如，若 n=lOO，则 m 最好取 l 1 3、127、139、143等素数另外，当关键字 K 为一个字符串时，需要把它设法转换为一个整数，然后再用这个整数整除以 m 得到余数，即散列地址下面的 Hash(K，m)函数就能够求出关键字 K 为字符串时的散列地址在这里，采用的把字符串 K 转换为整数的过程是：首先求出 K 的长度，即所含的字符个数，接着把每个字符的 ASCII 码(即该字符的整数值)累加到无符号整型量 h上，并在每次累加之前把 h 的值左移3个二进制位，即扩大8倍3．数字分析法数字分析法是取关键字中某些取值较分散的数字位作为散列地址的方法。

它适合于所有关键字已知，并对关键字中每一位的取值分布情况作出了分析例如，有一组关键字为(92317602，92326875，92739628，92343634，92706816，92774638，92381262， 92394220)，通过分析可知，每个关键字从左到右的第1，2，3位和第6位取值较集中，不宜作散列地址剩余的第4，5，7和8位取值较分散，可根据实际需要取其中的若干位作为散列地址若取最后两位作为散列地址，则散列地址的集合为(2，75，28，34，16，38，62，20)4．平方取中法平方取中法是取关键字平方的中间几位作为散列地址的方法，具体取多少位视实际要求而定一个数平方后的中间几位和数的每一位都有关从而可知，由平方取中法得到的散列地址同关键字的每一位都有关，使得散列地址具有较好的分散性平方取中法适应于关键字中的每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况 [Page]5．折叠法折叠法是首先将关键字分割成位数相同的几段(最后一段的位数若不足应补0)，段的位数取决于散列地址的位数，由实际需要而定，然后将它们的叠加和(舍去最高位进位)作为散列地址的方法例如一个关键字 K=68242324，散列地址为3位，则将此关键字从左到右每三位一段进行划分，得到的三段为682，423和240，叠加和为682+423+240=345，此值就是存储关键字为68242324元素的散列地址。

折叠法适应于关键字的位数较多，而所需的散列地址的位数又较少，同时关键字中每一位的取值又较集中的情况0顶一下。