哈希函数目前主要有以下几种类型:
1 直接定址法：
取关键字或关键字的某个线性函数值为哈希地址。即： H(key) = key 或 H(key) = a*key+b 哈希表及其概念
iis7站长之家：某大学从1960年开始招生，有历届招生人数统计表，其中 以年份为关键字。则哈希函数可设计为：H(key) = key - 1959 直接定址法由于关键字与存储地址存在一一对应关系，因此，不会 发生冲突现象。
举例:
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数。
2 除余法：
选择一个适当的正整数P（P≤表长），用P 去除关键字，取所得余数作为哈希地址。即：H(key) = key % P （P ≤ 表长） 除余法的关键是选取适当的P，一般选P为小于或等于哈希表的长 度m的某个素数为好。
例： m = 8，16，32，128，256，512 P = 7，13，31，127，251，503 除余法不仅可以直接对关键字取模，也可在折叠、平方取中等运算 之后取模。
3 平方取中法：
取关键字平方后的中间几位为哈希地址。由于一个数的平方的中间几位与这个数的每一位都有关，因而，平方取中法产生冲突的机会相对较小。平方取中法中所取的位数由表长决定。
例： K = 456 , K2 = 207936 若哈希表的长度m=102，则可取79（中间两位）作为哈希函数值。
4 折叠法：
把一个关键码分成位数相同的几段（最后一段的位数可以， 不同），段的长度取决于哈希表的地址位数，然后将各段的 叠加和（舍去进位）作为哈希地址。
折叠法又分为移位叠加和边界叠加两种。其中，移位叠加是将 各段的最低位对齐，然后相加；而边界叠加则是两个相邻的段沿边界来回折叠，然后对齐相加。
例：关键字K=58242324169，哈希表长度为1000，则将此关键字分成三位一段，两种叠加结果如下：582+ 423+ 241+69=315,582+324+ 241+96= 243
当关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以使用折叠法。
5 数字分析法：
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字中的若干位组成哈希地址。
例如:
有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
6 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
-
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载,整理或搜集自网络.欢迎任何形式的转载，转载请注明出处.
转载请注明：文章转载自:[169IT-IT技术资讯]
本文标题:哈希函数的构造方法及举例
