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

作者:青岛澄润国际贸易有限公司 来源:www.usabcc.com 发布时间:2017-09-12 16:32:00
Hash算法---多面哈希(算法+思想)

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

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

记录的关键字之间建立一个确定的对应关系函数 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),即发生冲突。

方法一:开放定址法:

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

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉做网站 https://www.feimao666.com

  • 上一篇:centos安装python
  • 下一篇:最后一页
  •