e彩cc国际网投平台登陆页 详解哈希表的查找

【时间: 2020-01-11 16:27:25】【字号:

e彩cc国际网投平台登陆页 详解哈希表的查找

e彩cc国际网投平台登陆页,哈希表和哈希函数

在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个关键字和一个存储位置能唯一对应。

这个映射函数称为哈希函数,根据这个原则建立的表称为哈希表(hash table),也叫散列表。

以上描述,如果通过数学形式来描述就是:

若查找关键字为 key,则其值存放在 f(key) 的存储位置上。由此,不需比较便可直接取得所查记录。

注:哈希查找与线性表查找和树表查找最大的区别在于,不用数值比较。

冲突

若 key1 ≠ key2 ,而 f(key1) = f(key2),这种情况称为冲突(collision)。

根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这一映射过程称为构造哈希表。

构造哈希表这个场景就像汽车找停车位,如果车位被人占了,只能找空的地方停。

构造哈希表

由以上内容可知,哈希查找本身其实不费吹灰之力,问题的关键在于如何构造哈希表和处理冲突。

常见的构造哈希表的方法有 5 种:

(1)直接定址法

说白了,就是小学时学过的一元一次方程。

即 f(key) = a * key + b。其中,a和b 是常数。

(2)数字分析法

假设关键字是r进制数(如十进制)。并且哈希表中可能出现的关键字都是事先知道的,则可选取关键字的若干数位组成哈希地址。

选取的原则是使得到的哈希地址尽量避免冲突,即所选数位上的数字尽可能是随机的。

(3)平方取中法

取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,仅取其中的几位为地址不一定合适;

而一个数平方后的中间几位数和数的每一位都相关, 由此得到的哈希地址随机性更大。取的位数由表长决定。

(4)除留余数法

取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。

即 f(key) = key % p (p ≤ m)

这是一种最简单、最常用的方法,它不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。

注意:p的选择很重要,如果选的不好,容易产生冲突。根据经验,一般情况下可以选p为素数。

(5)随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 f(key) = random(key)。

通常,在关键字长度不等时采用此法构造哈希函数较为恰当。

解决冲突

设计合理的哈希函数可以减少冲突,但不能完全避免冲突。

所以需要有解决冲突的方法,常见有两类

(1)开放定址法

如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。

当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。

例子

若要将一组关键字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。

采用除留余数法构造哈希表;采用开放定址法处理冲突。

不妨设选取的p和m为13,由 f(key) = key % 13 可以得到下表。

需要注意的是,在上图中有两个关键字的探查次数为 2 ,其他都是1。

这个过程是这样的:

a. 12 % 13 结果是12,而它的前面有个 25 ,25 % 13 也是12,存在冲突。

我们使用开放定址法 (12 + 1) % 13 = 0,没有冲突,完成。

b. 35 % 13 结果是 9,而它的前面有个 9,9 % 13也是 9,存在冲突。

我们使用开放定址法 (9 + 1) % 13 = 10,没有冲突,完成。

(2)拉链法

将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。

在这种方法中,哈希表中每个单元存放的不再是记录本身,而是相应同义词单链表的头指针。

例子

如果对开放定址法例子中提到的序列使用拉链法,得到的结果如下图所示:

实现一个哈希表

假设要实现一个哈希表,要求

a. 哈希函数采用除留余数法,即 f(key) = key % p (p ≤ m)

b. 解决冲突采用开放定址法,即 f2(key) = (f(key)+i) % size (p ≤ m)

(1)定义哈希表的数据结构

classhashtable{

publicintkey = 0;// 关键字

publicintdata = 0;// 数值

publicintcount = 0;// 探查次数

(2)在哈希表中查找关键字key

根据设定的哈希函数,计算哈希地址。如果出现地址冲突,则按设定的处理冲突的方法寻找下一个地址。

如此反复,直到不冲突为止(查找成功)或某个地址为空(查找失败)。

/**

* 查找哈希表

* 构造哈希表采用除留取余法,即f(key) = key mod p (p ≤ size)

* 解决冲突采用开放定址法,即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)

* ha为哈希表,p为模,size为哈希表大小,key为要查找的关键字

*/

publicintsearchhashtable(hashtable[]ha,intp,intsize,intkey){

intaddr = key % p;// 采用除留取余法找哈希地址

// 若发生冲突,用开放定址法找下一个哈希地址

while(ha[addr].key != nullkey && ha[addr].key != key){

addr = (addr + 1) % size;

if(ha[addr].key == key){

returnaddr;// 查找成功

}else{

returnfailed;// 查找失败

(3)删除关键字为key的记录

在采用开放定址法处理冲突的哈希表上执行删除操作,只能在被删记录上做删除标记,而不能真正删除记录。

找到要删除的记录,将关键字置为删除标记delkey。

publicintdeletehashtable(hashtable[]ha,intp,intsize,intkey){

intaddr = 0;

addr = searchhashtable(ha,p,size,key);

if(failed != addr){// 找到记录

ha[addr].key = delkey;// 将该位置的关键字置为delkey

returnsuccess;

}else{

returnnullkey;// 查找不到记录,直接返回nullkey

(4)插入关键字为key的记录

将待插入的关键字key插入哈希表

先调用查找算法,若在表中找到待插入的关键字,则插入失败;

若在表中找到一个开放地址,则将待插入的结点插入到其中,则插入成功。

publicvoidinserthashtable(hashtable[]ha,intp,intsize,intkey){

inti = 1;

intaddr = 0;

addr = key % p;// 通过哈希函数获取哈希地址

if(ha[addr].key == nullkey || ha[addr].key == delkey){// 如果没有冲突,直接插入

ha[addr].key = key;

ha[addr].count = 1;

}else{// 如果有冲突,使用开放定址法处理冲突

do{

addr = (addr + 1) % size;// 寻找下一个哈希地址

i++;

}while(ha[addr].key != nullkey && ha[addr].key != delkey);

ha[addr].key = key;

ha[addr].count = i;

(5)建立哈希表

先将哈希表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列依次插入。

publicvoidcreatehashtable(hashtable[]ha,int[]list,intp,intsize){

inti = 0;

// 将哈希表中的所有关键字清空

for(i = 0;i < ha.length;i++){

ha[i].key = nullkey;

ha[i].count = 0;

// 将关键字序列依次插入哈希表中

for(i = 0;i < list.length;i++){

this.inserthashtable(ha,p,size,list[i]);

完整代码

classhashtable{

publicintkey = 0;// 关键字

publicintdata = 0;// 数值

publicintcount = 0;// 探查次数

publicclasshashsearch{

privatefinalstaticintmaxsize = 20;

privatefinalstaticintnullkey = 1;

privatefinalstaticintdelkey = 2;

privatefinalstaticintsuccess = 0;

privatefinalstaticintfailed = 0xffffffff;

/**

* 查找哈希表

* 构造哈希表采用除留取余法,即f(key) = key mod p (p ≤ size)

* 解决冲突采用开放定址法,即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)

* ha为哈希表,p为模,size为哈希表大小,key为要查找的关键字

*/

publicintsearchhashtable(hashtable[]ha,intp,intsize,intkey){

intaddr = key % p;// 采用除留取余法找哈希地址

// 若发生冲突,用开放定址法找下一个哈希地址

while(ha[addr].key != nullkey && ha[addr].key != key){

addr = (addr + 1) % size;

if(ha[addr].key == key){

returnaddr;// 查找成功

}else{

returnfailed;// 查找失败

/**

* 删除哈希表中关键字为key的记录

* 找到要删除的记录,将关键字置为删除标记delkey

*/

publicintdeletehashtable(hashtable[]ha,intp,intsize,intkey){

intaddr = 0;

addr = searchhashtable(ha,p,size,key);

if(failed != addr){// 找到记录

ha[addr].key = delkey;// 将该位置的关键字置为delkey

returnsuccess;

}else{

returnnullkey;// 查找不到记录,直接返回nullkey

/**

* 将待插入的关键字key插入哈希表

* 先调用查找算法,若在表中找到待插入的关键字,则插入失败;

* 若在表中找到一个开放地址,则将待插入的结点插入到其中,则插入成功。

*/

publicvoidinserthashtable(hashtable[]ha,intp,intsize,intkey){

inti = 1;

intaddr = 0;

addr = key % p;// 通过哈希函数获取哈希地址

if(ha[addr].key == nullkey || ha[addr].key == delkey){// 如果没有冲突,直接插入

ha[addr].key = key;

ha[addr].count = 1;

}else{// 如果有冲突,使用开放定址法处理冲突

do{

addr = (addr + 1) % size;// 寻找下一个哈希地址

i++;

}while(ha[addr].key != nullkey && ha[addr].key != delkey);

ha[addr].key = key;

ha[addr].count = i;

/**

* 创建哈希表

* 先将哈希表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列依次插入。

*/

publicvoidcreatehashtable(hashtable[]ha,int[]list,intp,intsize){

inti = 0

// 将哈希表中的所有关键字清空

for(i = 0;i < ha.length;i++){

ha[i].key = nullkey;

ha[i].count = 0;

// 将关键字序列依次插入哈希表中

for(i = 0;i < list.length;i++){

this.inserthashtable(ha,p,size,list[i]);

/**

* 输出哈希表

*/

publicvoiddisplayhashtable(hashtable[]ha){

inti = 0;

system.out.format("pos:\t","pos");

for(i = 0;i < ha.length;i++){

system.out.format("%4d",i);

system.out.println();

system.out.format("key:\t");

for(i = 0;i < ha.length;i++){

if(ha[i].key != nullkey){

system.out.format("%4d",ha[i].key);

}else{

system.out.format(" ");

system.out.println();

system.out.format("count:\t");

for(i = 0;i < ha.length;i++){

if(0 != ha[i].count){

system.out.format("%4d",ha[i].count);

}else{

system.out.format(" ");

system.out.println();

publicstaticvoidmain(string[]args){

int[]list = {3,112,245,27,44,19,76,29,90};

hashtable[]ha = newhashtable[maxsize];

for(inti = 0;i < ha.length;i++){

ha[i] = newhashtable();

hashsearch search = newhashsearch();

search.createhashtable(ha,list,19,maxsize);

search.displayhashtable(ha);

参考资料

《数据结构习题与解析》(b级第3版)

转自:静默虚空

http://www.cnblogs.com/jingmoxukong/p/4332252.html

-----这里是数学思维的聚集地------

“超级数学建模”(微信号supermodeling),每天学一点小知识,轻松了解各种思维,做个好玩的理性派。50万数学精英都在关注!