哈希函数的构造方法

数字关键字的哈希函数构造方法

对于数字类型的关键字，哈希函数有以下几种常用的构造方法：

直接定址法

取关键字的某个线性函数值为散列地址。

$$h(key) = a * key + b$$

例如根据出生年份计算人口数量h(key) = key - 1990：

地址	出生年份	人数
0	1990	1285万
1	1991	1281万
2	1992	1280万
$\dots$	$\dots$	$\dots$
10	2000	1250万
$\dots$	$\dots$	$\dots$
21	2011	1180万

直接定址法

知识测验

重做

题目

出生年份用 h(key) = key − 1990 直接定址，2006 年的地址是什么？

A2006B16C1990D6

 

除留余数法

哈希函数为h(key) = key % p，p一般取素数。

例如h(key) = key % 17：

除留余数法

知识测验

重做

题目

h(key) = key % 17 时，34 和 51 会发生什么？

A分别落在 2 和 3B分别落在 0 和 1C两者都映射到 0，需要处理冲突D取素数就保证没有冲突

 

数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址。

例如取11位手机号码的后4位作为地址h(key) = key % 10000。

再例如取18位身份证号码中变化较为随机的位数：

数字分析法

折叠法

把关键字分割成位数相同的几个部分，然后叠加。

例如将整数56793542每三位进行分割：

运算	数值
	542
	793
+	056
=	1391

$$h(56793542) = 391$$

知识测验

重做

题目

56793542 按三位分组为 056、793、542，加和后取末三位，地址是什么？

A319B1391C542D391

 

平方取中法

计算关键字的平方，取中间几位。

例如整数56793542：

运算	数值
	56793542
*	56793542
=	3225506412905764

$$h(56793542) = 641$$

字符串关键字的哈希函数构造方法

对于字符串类型的关键字，哈希函数有以下几种常用的构造方法：

ASCII码加和法

$$h(key) = \left(\sum key[i] \right)\bmod N$$

但是对于某些字符串会导致严重冲突，例如：a3、b2、c1或eat、tea等。

知识测验

重做

题目

ASCII 码加和法为什么会使 eat 和 tea 冲突？

A加和只依赖字符总和，不区分字符顺序B它只读取第一个字符C它完全忽略字符值D两个单词的长度不同

 

移位法

取前3个字符移位。

$$h(key) = \left(key[0] \times 27^2 + key[1] \times 27 + key[2] \right)\bmod N$$

对于一些字符串仍然会冲突，例如string、strong、street、structure等。

一个有效的改进是涉及关键字中所有n个字符：

$$h(key) = \left( \sum_{i=0}^{n-1} key[n-i-1] \times 32^i \right)\bmod N$$

互动实验

字符串散列：逐字符计算与比较

重置实验访问权限PRO

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

动手练习

折叠法：计算一组新关键字的地址

简单·8 分钟查看参考答案

只使用折叠法，处理关键字序列 724186035、186035724、905417236。每个关键字从右向左按三位分组，将各组相加，再取末三位作为地址：h(key) = 分组之和 % 1000。

1. 写出每个关键字的分组、加和过程与最终地址。
2. 指出哪些关键字发生冲突，并解释原因。