hash 算法基础

hash 算法基础

首先来看一下什么是hash

hash 实际上就是一个映射函数 ,使得把某一个不满足条件的量(可能难于存储 可能没法表示)映射到一个满足条件的量上 举个简单的例子理解一下 : 某学校要对2014级新生进行入学成绩统计 要用数组来存储学生的信息 而大家的学号都是 2014**** 这样的形式且每人的学号唯一确定  那么如果开一个数组大小为  20150000肯定是足够我们使用了 ,不过 在这个大数组里 ,最多只用了 10000个值,所以我们考虑用一个后四位作为存储的数组下标而不是整个学号 这其实就是一个hash的思想  我们相当于建立了一个hash函数 f(x)=x%10000 这样的话我们节省了空间 同样也使效率变得高

最简单的hash思想 桶排序 参见 HDU 的 1425题 (排序复杂度可以简化到 n)

冲突

我们通过上面学生的例子 能够发现,一个理想的hash函数应该是个一一映射的函数 即仅存在唯一一组y,x使得f(x)=y 但是 ,实际使用的时候 ,hash函数的这个性质很难保证甚至根本不能保证 举个例子 :把1000000个数映射到100个hash表上 (hash表就是指存hash映射关系的那个数组) 那么 一定会有多个不同值映射到了一个地址上 ,这样的现象叫做 冲突(collision)   那么如何解决冲突就成为了很重要的问题 我们在这里介绍几个方式 主要介绍第一个方式 线性探测再散列

线性探测再散列

这个方法的思想就是 如果遇到了冲突,那么就去查找它的下一个地址处是否已经有值,一直走下去 (走到头的话就回到数组首端) 直到遇到没有值的地方或者是又再次回到了f(k)处 结束循环 成功找到的话把值放进去 ,否则hash散列失败 举个例子如下

我们对这六个数字进行散列操作 有

23%7=2 46%7=4 19%7=5 55%7=6 38%7=3 233%7=2 我们会发现 在地址2处产生了冲突,因此我们使用线性探测再散列 按照由左到右的顺序来执行hash 在处理233之前的结果为下图

这时 由于f(233)=2但是 2处已经有值 所以 执行下面操作 :逐次循环后移直到找到hash表内值为空的地方再放入233 结果就是 :

这就是线性探测再散列法处理冲突

代码如下

int hash[MOD];						//存储映射关系
int num[MOD];						//检查hash表该位置是否为空 0表示空 

int genhash(int n)
{
	int tmp=n%MOD;
	if(tmp<0) tmp+=MOD;
	while(hash[tmp]!=n && num[tmp]!=0)
	{
		tmp=(tmp+1)%MOD;
	}
	return tmp;
}

 

其它方式处理冲突

除了线性探测 我们还有

  1. 平方探测再散列 如果冲突则查看 addr+-1 +-4 +-9 …直到找到空位置为止
  2. 随机探测再散列 如果冲突则查看 addr+-一伪随机整数 直到找到空位置位置
  3. 再哈希法 顾名思义 再次对这个地址值用一个hash函数来处理
  4. 链地址法 把hash值相同的元素都存在同一个链表中
  5. 公共溢出区 ,这个是很实际中应用广泛的实用的方式,建立一个二维表,原理与链地址法相通,不过,这个是有限长度,那么为了处理个别的超出长度的量,建立一个溢出区来处理
以上是我对hash的一点理解和解读 请大神们看了多多批评指正  _(・ω・」 ∠)__(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_爬呀爬_(・ω・」 ∠)_ _(・ω・」 ∠)_ 我们中出了两个叛徒!

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

14 + 5 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.