常见hash算法介绍

哈希算法进行查找的基本原理是根据总体数据量预先设置一个数组,使用一个哈希函数并以数据的关键字作为自变量,得到唯一的返回值。这样就可以利用哈希函数将数据元素映射到数组的某一位置并把数据存放在对应位置上。在查找时,通过哈希函数计算该数据应该存储在哪里,再到相应的存储位置取出查找的数据。

哈希是一种高效查找算法,也是一种高效的存储算法。哈希算法是在时间和空间上做出权衡的经典例子。如果没有存储的限制,我们可以直接将关键字作为数组的索引,那么所有查找操作只需要访问内存一次即可完成。但是这种理想情况只在数据量较小时可以应用,而当数据量很大时需要的内存则会太大。哈希算法是在空间和时间的开销之间找到了一种平衡。

因此,设计一个好的哈希函数是重中之重,好的哈希函数应该使每个关键字都尽可能地散列到每一个位置中去。我们面对的第一个问题就是如何设计一个易于计算并且均匀分布所有的键的哈希函数。这一节将会介绍除法哈希算法、乘法哈希算法、平方取中法、随机数哈希算法。

除法哈希算法

先来看第一个哈希函数:除法哈希。用每一个关键字去除以一个特定的质数,所得的余数就是该关键字的哈希值。通过 x 除以 m 的余数将关键字映射到数组的 m 个位置中。

哈希函数公式为:

h(x)=xmodm


例如,有一组数据 3、11、8、6 需要存储,哈希函数为 h(x)=xmod 7。关键字 8 的计算过程如下:
h(8)=8 mod 7
    h (8)=1

其他关键字的计算过程类似,那么利用哈希函数存储的数据如图 1 所示,注意数组下标从 0 开始。
哈希函数示例(1)
图 1:哈希函数示例(1)

在选择 m 的值时,尽量选择质数,免得出现过多的多个关键字映射到同一个位置的情况,降低哈希函数的效率。按照统一的哈希函数存储数据,也按照统一的哈希函数查找数据,按照这种方法查找数据,理论上可以达到常数级别的查找效率。

除法哈希函数速度相对较快,只需一次求余运算即可。哈希算法和关键字的类型有关。最好的情况是,每种类型的关键字都需要一个与之对应的哈希函数。在上面的例子中关键字是数字,比如身份证号就可以直接使用这个哈希函数。

但是实际的应用中会有很多不是数字的情况,那么我们应该找到一种将它们解释为数字的方法。例如,在做学生成绩的哈希映射时,把学生的姓名作为关键字,我们可以采用把名字的ASCII码相加的方式,就转换成了数字版本的关键字。

乘法哈希算法

对给定的长度为 m 的数组,用关键字 x 乘以一个常数 N,N 的值为大于 0 并小于 1 的一个小数,并提取出 Nx 的小数部分。之后,用 m 乘以这个小数,再向下取整。

哈希函数公式为:
哈希函数公式
其中 Nx mod1 的意思就是 Nx 的小数部分。相对于除法哈希算法,乘法哈希算法对于数组的长度 m 没有过多的要求。研究表明,N 的值为 0.618 较好。

例如,关键字 8 需要存储,哈希函数为 ,计算过程如下:
哈希函数计算过程

那么利用哈希函数存储的数据如图 2 所示,注意数组下标从 0 开始。
哈希函数示例(2)
图 2:哈希函数示例(2)

平方取中法

平方取中法,首先计算出关键字的平方值,然后取平方值中间几位作为哈希地址。

哈希函数公式为:

h(x)=mid(x⋅x,n)

其中 mid 的意思就是选取中间 n 位的函数。

例如,关键字的集合为 {123,234,245},它们对应的平方值为 {15129,54756,60025},如果我们选择平方值的千位和百位作为哈希值,则它们的哈希值为 {51,47,0}。

例如,关键字 245 需要存储,哈希函数为 h(x)=mid(x⋅x,2),计算过程如下:

h(245)=mid(245 x 245,2)
h(245)=mid(60025,2)
h(245)=0

 
那么利用哈希函数存储的数据如图 3 所示,注意数组下标从 0 开始。
哈希函数示例(3)
图 3:哈希函数示例(3)

随机数哈希算法

选择一个随机函数,以关键字作为随机函数的种子,然后以随机函数的返回值作为该关键字的哈希值。

通常情况下,当关键字的长度不等且不规则时采用这种方法。