哈希查找的解决冲突

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：

(1) 开放地址法

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

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

(2) 链地址法

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

例3. 6是一个简单的哈希查找算法程序，你可以将首启它和本章结尾的有关代码一起编译连接成一个可执行程序。

例3．6一个简单的哈希查找算法程序

1: #include<stdlib.h>

2: #include<string.h>

3: #include list.h

4: #include hash.h

5:

6: #define HASH_SIZE 1024

7:

8: static listnode_t *hashTable[HASH_SIZE]

9:

10: void insert(const char * s)

11: {

12: listnode_t *ele = newNode((void * ) s)

13: unsigned int h = hash(s) % HASH_SIZE

14:

15: ele->next = hashTable[h]

16: hashTable[h] = ele

17: }

18:

19: void print (void)

20: {

21: int h

22:

23: for (h = 0h <HASH_SIZEh++)

24: {

25: listnode_t * lp = hashTalbe[h]

26:

27: if(lp == NULL)

28: continue

29: printf([%d] , h)

30: while (lp)

31: {

32: printf(\t'%s' , lp->u.str)

33: lp = ip->next

34: }

35: putchar ('\n')

36: }

37: }

38:

39: const char *search(const char *s)

40: {

39: unsigned int h = hash(s) % HASH_SIZE

42: listnode_t * lp = hashTable[h]

43:

44: while (lp)

45: {

46: if (! strcmp (s, lp->u.str))

47: return lp->u.str

48: lp = lp->next

49: }

50: return NULL

51: }

请参见：

3. 4 哪一种查找方法最方便?

3．5 哪一种查找方法最快?

3．8 怎样查找链表早芹樱中的数据?

_____________________________________________

以下是一个简单示例：

#include<iostream>

#include<string>

using namespace std

#define m 5 //人数

#define n 10 //哈希表长度

#define q 7 //随机数

struct name{

char *py

int k

}

name namelist[n]

struct hash{

char *py

int k

int s

}

hash hashlist[n]

void listname()

{

char *f

int s0,r,i

namelist[0].py=as

namelist[1].py=sa

namelist[2].py=d

namelist[3].py=f

namelist[4].py=g

for(i=0i<mi++)

{

s0=0

f=namelist[i].py

for(r=0*(f+r)!='\0'r++)

s0+=*(f+r)

namelist[i].k=s0

}

}

void creathash()

{

int i

for(i=0i<ni++)

{

hashlist[i].py=

hashlist[i].k=0

hashlist[i].s=0

}

for(i=0i<mi++)

{

int sum=0

int adr=(namelist[i].k)%q

int d=adr

if(hashlist[adr].s==0)

{

hashlist[adr].py=namelist[i].py

hashlist[adr].k=namelist[i].k

hashlist[adr].s=1

}

else

{

while(hashlist[d].k!=0)

{

d=(d+namelist[i].k%5+1)%q

sum+=1

}

hashlist[d].py=namelist[i].py

hashlist[d].k=namelist[i].k

hashlist[d].s=sum+1

}

}

}

void find()

{

string nam

int s0=0,r,sum=1,adr,d

cout<<请输入姓名的拼音：<<endl

cin>>nam

for(r=0r<20r++)

s0+=nam[r]

adr=s0%q

d=adr

if(hashlist[adr].k==s0)

cout<<姓名:<<hashlist[d].py<<<<关键字:<<s0<<<<查找长度为: 1<<endl

else if(hashlist[adr].k==0)

cout<<无此记录！<<endl

else

{

int g=0

while(g==0)

{

d=(d+s0%5+1)%q

sum+=1

if(hashlist[d].k==0)

{

cout<<无此记录！<<endl

g=1

}

if(hashlist[d].k==s0)

{

cout<<姓名:<<hashlist[d].py<<<<关键字:<<s0<<<<查找长度为: 1<<endl

g=1

}

}

}

}

void display()

{

int i

float av=0

for(i=0i<ni++)

{

cout<<姓名:<<hashlist[i].py<<<<关键字:<<hashlist[i].k<<搜索长度：<<hashlist[i].s<<endl

}

for(i=0i<7i++)

{

av+=hashlist[i].s

}

av/=m

cout<<平均查找长度：=<<av<<endl

}

int main()

{

char x

listname()

creathash()

cout<<d. 显示哈希表 f. 查找 任意键退出 请选择：<<endl

while(cin>>x){

if(x=='d'){display()cout<<endl}

else if(x=='f'){find()cout<<endl}

else break

}

return 0

}

以上讲的查找方法基于比较的,查找效率依赖比较次数,其实理想的查找希望不经比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,这样查找k时,只要根据这个对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存储时容易冲突（弊族collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。

1.哈希函数的构造方法

直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)

如:人口数字统计表

地址 1 2 3 ... 100

年龄 1 2 3 ... 100

人数 67 3533 244 ... 4

数字分析法:取关键字的若干数位组成哈希地址

如：关键字如下：若哈希表凳御长为100则可取中间两位10进制数作为哈希地址。

81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537

平方取中法：关键字平方后取中间几位数组成哈希地址

折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。

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

H(k)=k mod p p<=m

随机数法：H(k)=rondom(k)。

2.处理冲突的租粗弊方法

假设地址集为0..n-1,由关键字得到的哈希地址为j(0<=j<=n-1)的位置已存有记录,处理冲突就是为该关键字的记录找到另一个"空"的哈希地址。在处理中可能得到一个地址序列Hi i=1，2，...k

0<=Hi<=n-1),即在处理冲突时若得到的另一个哈希地址H1仍发生冲突,再求下一地址H2,若仍冲突,再求H3...。怎样得到Hi呢？

开放定址法：Hi=(H(k)+di) mod m （H(k)为哈希函数；m为哈希表长；di为增量序列）

当di=1，2，3，... m-1 时叫线性探测再散列。

当di=12，-12，22，-22，32，-32，...,k2,-k2时叫二次探测再散列。

当di=random（m）时叫伪随机探测序列。

例：长度为11的哈希表关键字分别为17，60，29，哈希函数为H(k)=k mod 11,第四个记录的关键字为38，分别按上述方法添入哈希表的地址为8，4，3（随机数=9）。

再哈希法：Hi=RHi(key) i=1,2,...,k,其中RHi均为不同的哈希函数。

链地址法：这种方法很象基数排序，相同的地址的关键字值均链入对应的链表中。

建立公益区法：另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表。

3.哈希表的查找

例:如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

14 01 68 27 55 19 20 84 79 23 11 10

当给定值k=84,则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。

当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记录。

5.5 查找第k小元素

查找第k小元素即在n个元素中（未排序）找到第k小的元素。方法同快速排序，采用递归方式。

程序如下：

program kspv

const n=7

type

arr=array[1..n] of integer

var

b:arr

i,k:integer

function p(s,t:integer):integer

var i,j,t1,x:integer

begin

i:=sj:=tx:=b[i]

repeat

while (b[j]>=x) and (j>i) do j:=j-1

if j>i then begin t1:=b[i]b[i]:=b[j]b[j]:=t1end

while (b[i]<=x) and (i<j) do i:=i+1

if i<j then begin t1:=b[j]b[j]:=b[i]b[i]:=t1end

until i=j

b[i]:=x

p:=i

end

function find(s,t,k:integer):integer

var p1,q:integer

begin

if s=t then find:=b[s] else

begin

p1:=p(s,t)

q:=p1-s+1

if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q)

end

end

begin

write('input data:')

for i:=1 to n do read(b[i])readln

write('input k:')read(k)

write('output data:')

writeln('kthsmall:=',find(1,n,k))

end.

希望你运用成功