二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(20)

9.4.2 散列函数构造散列函数的所寻求的目标就是使散列地址尽可能均匀地分布在散列空间上，即把诸关键字尽可能均匀地映射到基本区域0 ～ m-1之中，这样冲突才会尽可能减少。同时还要使散列函数的计算尽可能简单，以节省计算时间。根据关键字的结构和分布的不同，可构造出与之相适应的散列函数，这里只介绍较常用的几种。在下面的讨论中，假定关键字均为正整数，因为若不然，则可把它们转换成正整数；散列函数映射的基本区域为0 ～ m-1。⒈ 除留余数法除留余数法 modulo-division method 简称除余法，是一种既简单又常用的方法，它是利用关键字key除以小于等于散列表长度m的正整数p所得余数来作为散列地址，即h key key % p p≤m此种方法的关键是p值的选择要适当。下面来分析一下如何选择p的问题：① 如果选取p为偶数，那么当key为偶数时，h key 也为偶数；当key为奇数时，h key 也为奇数，这在很多表中会导致一种很大的偏向，致使冲突增多。② 如果选取p为关键字的基数的幂次，那么就等于是选取关键字的最后若干位作为地址，而与高位无关。这样就导致高位不同而低位相同的关键字互为同义词。

例如，对于关十进制数的关键字座机电话号码，座机电话号码，座机电话号码，…，若选取p为103 1000 ，则列出的这些关键字均互为同义词。一般地，p应选取为小于等于散列表基本区域长度m的最大素数。例如：m 8, 16, 32, 64, 128, 256, 512, 1024, …p 7, 13, 31, 61, 127, 251, 503, 1019, …⒉ 数字分析法设有n个d位数的关键字，每一位可能出现有s个不同的符号 例如十进制数，每一位可有0, 1, …, 9十个不同的符号 ，此s个符号在各位上出现的频率不一定相同，可能在某些位上分布较为均匀，即每个符号出现的次数都接近n/s，而在另一些位上分布较不均匀，选择其中分布均匀的d' d 位作为散列地址，这便是数字分析法 digit ysis method 。例9.21 假设十进制数的关键字的位数为8，散列表的基本区域的范围为0 ～ 99。对于图9-34给出的一些关键字，若采用数字分析法来计算散列函数值，则应从这些关键字中选取数字分布较为均匀2位来作为散列地址 详见图9-34 。⒊ .折叠法折叠法 folding method 的处理方法是：如果关键字的位数较多，可将关键字从某些地方断开，把关键字分为几个部分，其中至少有一段的长度等于散列地址的位数，然后取把其余部分加到它的上面，如果最高位有进位，则把进位丢掉。

例9. 22 假设十进制数的关键字的位数为9，散列表的基本区域的范围为0 ～ 9999。对于图9-35给出的关键字座机电话号码5，采用不同的方法分段、折叠和相加，就可得到不同的散列地址 详见图9-35 。⒋ 平方取中法平方取中法 mid-square method 或称中平方法。其方法是：先通过求关键字的平方值来扩大关键字之间的差别，然后根据表的长度取中间几位作为散列地址。由于一个数的平方后的中间几位与数的每一位都相关，因此所得到的散列地址分布得较为均匀。例如，key 9452，平方后得座机电话号码，如果散列地址位数为4位，可取中间的4位数字3403作为散列地址。⒌ 随机数法随机数法 pseudo-random method 适用于关键字长度不等的情况。通常散列函数可定义为h key m*random key其中random 为随机函数，它产生0 ～ 1之间的随机数。因为散列地址应为0 ～ m-1之间的整数值，所以产生的随机数乘上比例因子m后再向下取整，就能确保得到的散列函数值落入表的基本区域0 ～ m-1的范围之内。在实际应用中需视不同的情况来采用不同的散列函数。通常考虑的因素有：① 散列函数本身计算所需要的时间；② 关键字的类型与长度；③ 散列表的大小；④ 关键字的分布情况等。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-20.html