哈希函数（一）-直接定址法、除留余数法、平方取中法

哈希函数

哈希函数：将哈希表中元素的关键键值映射为元素存储位置的函数。 哈希函数是哈希表中最重要的部分。一般来说，哈希函数会满足以下几个条件：

• 哈希函数应该易于计算，并且尽量使计算出来的索引值均匀分布，这能减少哈希冲突
• 哈希函数计算得到的哈希值是一个固定长度的输出值
• 如果 Hash(key1) 不等于 Hash(key2)，那么 key1、key2 一定不相等
• 如果 Hash(key1) 等于 Hash(key2)，那么 key1、key2 可能相等，也可能不相等（会发生哈希碰撞）

在哈希表的实际应用中，关键字的类型除了数字类型，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。一般会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。 而关于整数类型的关键字，通常用到的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。

下面介绍几个常用的哈希函数方法。

直接定址法

直接定址法：取关键字或者关键字的某个线性函数值为哈希地址。即：Hash(key)=key或者Hash(key)=a∗key+b，其中 a 和 b 为常数。

这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。

举一个例子，假设有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字，哈希函数取关键字自身，如下表所示。

比如想要查询 25 岁的人有多少，则只要查询表中第 25 项即可。

除留余数法

除留余数法：假设哈希表的表长为 m，取一个不大于 m 但接近或等于 m 的质数 p，利用取模运算，将关键字转换为哈希地址。即：Hash(key)=key，其中 p 为不大于 m 的质数。

这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。

比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中（长度为 11 的数组），通过除留余数法将这 7 个数应分别位于如下地址：

比如432，对11取余数，余数为3，放在03位置

平方取中法

平方取中法：先通过求关键字平方值的方式扩大相近数之间的差别，然后根据表长度取关键字平方值的中间几位数为哈希地址。

比如：Hasℎ(key)=(key∗key)//100%1000，先计算平方，去除末尾的2位数，再取中间 3 位数作为哈希地址。 这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。

比如关键字为1443， 进行哈希计算：

1443∗1443=2082249

2082249/100=20822

20822%1000=822

因此最终的哈希值结果就是822