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表的具体实现以及常见问题的解决方案,比如冲突的解决方法实现...

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