首页 > 程序开发 > 综合编程 > 其他综合 >

Hash算法---多面哈希(算法+思想)

2015-09-03

Hash算法是十分强大的查找算法。 在这里我总结了《大话数据结构》 && 《数据结构与算法》&& 网上的资源写出了多角度的Hash算法。 哈希查找平均时间O(1) 那么,什么是哈希查找呢? 在弄清楚什么是哈希查找之

Hash算法是十分强大的查找算法。

在这里我总结了《大话数据结构》 && 《数据结构与算法》&& 网上的资源写出了多角度的Hash算法。

哈希查找平均时间O(1).

那么,什么是哈希查找呢?

在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和

记录的关键字之间建立一个确定的对应关系函数 f,使得每个关键字key对应一个存储位置f(key)。

查找时,根据这个确定的对应关系找到给定值的映射f(key),若查找集合中存在这个记录,则必定

在f(key)的位置上。哈希技术既是一种存储方法,也是一种查找方法。

众所周知,哈希的速度是灰常快的,敢号称时间复杂度为O(1)的,呵呵,它和快排有一拼(目前只有快排敢叫“快排”这个名号)。而且,它偏偏还非常好用,这注定了它不平凡的存在。倒是目前网说哈希时,多是介绍各种哈希函数的构造及如何避免冲突,然后动不动就扯到MD5这些东西上去了。

其实哈希算法的应用十分广泛,首先说操作系统中数字 -1 , 0, 1 对应着不同的功能键,这就是一种哈希。

先来看看这个常见的东西吧:
如果n大于5就输出”Yes”,否则输出”No”,不用说,马上写出了这样的语句:

if (n > 5) {
	printf(Yes);
} else {
	printf(No);
}
如果写成一行也就是:

printf(n > 5? “Yes”: “No”);  

那现在,用哈希这样写:

char hash[2][] = { “No”, “Yes” };
printf(hash[n > 5]);

怎么样,强大吧。下来个例题:

1.按ascii码哈希
字符串中去掉指定字母。
例如:s:”hello world”去掉t:”aeiou”中字母后为”hll wrld”。
相信这种简单问题,对高手来说不是问题,但咱就从这说起。
首先说这个题一般人会这样写:

char s[] = hello world;
char t[] = aeiou;
int i, j, len;
for (i = len = 0; s[i]; i++) {
	for (j = 0; t[j]; j++) {
		if (s[i] == t[j])
			break;
	}
	if (!t[j])
		s[len++] = s[i];
}
s[len] = 0;
printf(s); 


如果用哈希思想

char s[] = hello world;
char t[] = aeiou;
char hash[128];
int i, len;
memset(hash, 0, sizeof(hash));
for (i = 0; t[i]; i++) {
	hash[t[i]] = 1;
}
for (i = len = 0; s[i]; i++) {
	if (!hash[s[i]])
		s[len++] = s[i];
}
s[len] = 0;
printf(s);

时间复杂度降低了

以及在数据结构中的使用:

构造方法:

1,直接定址法:

函数公式:f(key)=a*key+b (a,b为常数)

这种方法的优点是:简单,均匀,不会产生冲突。但是需要事先知道关键字的分布情况,适合查找表较小并且连续的情况。

2,数字分析法:

比如我们的11位手机号码“136XXXX7887”,其中前三位是接入号,一般对应不同运营公司的子品牌,如130是联通如意通,136是移动神州行,153是电信等。中间四们是HLR识别号,表示用户归属地。最后四们才是真正的用户号。

若我们现在要存储某家公司员工登记表,如果用手机号码作为关键字,那么极有可能前7位都是相同的,所以我们选择后面的四们作为哈希地址就是不错的选择。

3,平方取中法:

故名思义,比如关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227作为哈希地址。

4,折叠法:

折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些),然后将这几部分叠加求和,并按哈希表表长,取后几位作为哈希地址。

比如我们的关键字是9876543210,哈希表表长三位,我们将它分为四组,987|654|321|0 ,然后将它们叠加求和987+654+321+0=1962,再求后3位即得到哈希地址为962,哈哈,是不是很有意思。

5,除留余数法:

函数公式:f(key)=key mod p (p<=m)m为哈希表表长。

这种方法是最常用的哈希函数构造方法。

6,随机数法:

函数公式:f(key)= random(key)。

这里random是随机函数,当关键字的长度不等是,采用这种方法比较合适。

两种哈希函数冲突解决方法:

我们设计得最好的哈希函数也不可能完全避免冲突,当我们在使用哈希函数后发现两个关键字key1!=key2,但是却有f(key1)=f(key2),即发生冲突。

方法一:开放定址法:

开放定址法就是一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总是能找到,然后将记录插入。这种方法是最常用的解决冲突的方法。

相关文章
最新文章
热点推荐