Question

哈希函数构造方法

Answer 1

哈希函数构造方法有：直接定址法，数字分析法。

1.直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即：H（key）=key或H（key）=akey+b， 其中a和b为常数（这种哈希函数叫做自身函数）。

例如：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。标图1直接定址哈希函数例之一题，这样,若要询问25岁的人有多少，则只要查表的第25项即可。

2.数字分析法

假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

例如有80个记录，其关键字为8位十进制数。假设哈希表的表长为100%，则可取两位十进制数组成哈希地址。'取哪两位？原则是使得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列对关键字全体的分析中我们发现。

第①②位都是“81”，第③位只可能取1、2、3或4，第⑧位只可能取2，5或7，因此这4位都不可取。由于中间的4位可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

什么是哈希函数

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。