Hash 算法详细介绍与实现 (一)

前言

什么是 Hash?

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入(又叫做预映射， pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Hash 表(HashTable)又称散列表,通过把关键字 Key 映射到数组中的一个位置来访问记录,以加快查找速度,这个映射函数称为 Hash 函数,存放记录的数组称为 Hash 表.散列表是散列函数的一个主要应用(注意:关键字不是像在加密中所使用的那样是秘密的，但它们都是用来"解锁"或者访问数据的。)例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

Hash 函数是什么?

Hash 函数的作用是把任意长度的输入,通过 Hash 算法变换成固定的长度输出,该输出就是 Hash 值,这种转换是一种压缩映射,即是 Hash 值的空间通常远远小于输入的空间,不同的输入可能会散列成

散列表的散列函数几乎不可能或不切实际的理想是把每个关键字映射到唯一的索引上，因为这样能够保证直接访问表中的每一个数据。

一个好的散列函数(包括大多数加密散列函数)具有均匀的真正随机输出，因而平均只需要一两次探测(依赖于装填因子)就能找到目标。同样重要的是，随机散列函数几乎不可能出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的,影响产生冲突多少有以下三个因素:

1.散列函数是否均匀

2. 处理冲突的方法

3.散列表的装填因子

处理冲突的具体处理方法有:

1.开放寻址法:Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中 H(key)为散列函数，m 为散列表长，di 为增量序列，可有下列三种取法:

1. di=1,2,3,…，m-1，称线性探测再散列

2. di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列

3. di=伪随机数序列，称伪随机探测再散列

2. 再散列法:Hi=RHi(key),i=1,2,…，k RHi 均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生"聚集"，但增加了计算时间。

3. 链地址法(拉链法)

4. 建立一个公共溢出区

Hash 函数的应用

由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。比如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个"单向"操作:对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如 MD5，被广泛用作检验散列函数。hash 函数的应用一般有错误校正,语音识别,信息安全(文件校验,数字签名,鉴权等)等相关方面

Hash 算法

关键字 k 可能是整数或者字符串,可以按照关键字的类型设计不同的 Hash 算法,整数关键字的 Hash 算法常见的大概有以下几种:

• 直接取余法:f(x):= x mod maxM ; maxM 一般是不太接近 2^t 的一个质数。

• 乘积取整法:f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于实数。

• 平方取中法:f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。

直接取余法

直接取余法原理比较简单,直接用关键字 k 除以 Hash 表的大小 m 取余数,具体公式如下:

h(k) = k mod m

比如:如果 hash 表的大小 m=12,关键字 k 为 100,则 h(k)=4,这种算法只需要一个求余数操作.速度较快

乘积取整法

乘积取整法首先使用关键字 k 乘以一个常数 A(0<A<1),并抽取出 kA 的小数部分,然后用 hash 表大小 m 乘以这个值,再取整数部分即可.具体公式如下:

h(k) = floor(m * (kA mod 1))

其中 kA mod 1 表示 kA 的小数部分,floor 是取整的操作,当关键字是字符串的时候,就不能使用这个 Hash 算法,因为字符串是由字符组成,所以可以把字符串所有字符的 ASCII 码做加法操作,得到一个整数,接着再按照这个算法取计算就可以

具体实现如下:这里使用的是 php 的代码:

function hash($k, $m){	$strlen = strlen($k);	$hashval = 0;
	for($i = 0; $i<$strlen; $i++){		$hashval += ord($k{$i});	}		return $hashval % $m;//根据公式计算}

虽然这个算法很简单,而且效果不好.但是可以完整描述 Hash 算法的基本原理

经典的 Hash 算法

经过计算机科学家们多年的研究和探索,创造了一些很有成效的 Hash 算法.比较有名的包括:ELFHash、APHash 还有 Times33 等等。接着我们来看看这些经典算法中的代表 Times33 的实现代码：

unsigned int DJBHash(char *str){	unsigned int hash = 5381;  while(*str){    hash += (hash<<5) + (*str++);
  }  return (hash & 0x7FFFFFFF);
}

Times33 这个算法思路就是不断乘以 33,其效率和随机性都极其好,它广泛运用于多个开源项目,比如我们常用的 Web 服务器 Apache,Perl 以及 PHP 等等

本文着重介绍 Hash 算法原理以及它的应用和常见问题以及常见问题的解决方法;接下来第二部分会着重介绍 Hash 表的具体实现以及常见问题的解决方案,比如冲突的解决方法实现...

欲知后事如何,请听下回分解~