解决冲突的方法为链地址法

㈠ 数据结构

补充问下,这是个创建hashtable的函数,题目各个变量也没有描述清楚,请提问者审查,以减少回答者不必要的猜测.

㈡ 请列举四种处理哈希冲突的方法

1、开放地扯法
2、再哈希法
3、链地址法
4、建立一个公共溢出区

㈢ 设哈希函数为h(key)=key%19, 解决冲突的方法是链地址方法，设计一个从哈希表中删除关键字为key的一个记录的

int delete(int *s,int key)
{
int flag=0;

if(s==NULL)
return flag;

int *p,*q,loc;
loc=key%19;

if(s[loc]->next==NULL)
return flag;

p=s[loc];
while(p->next->next!=NULL)
{
if(p->next->data==key)
{
q=p->next;
p->next=q->next;
free(q);
flag=1;
}
p=p->next;
}

if(p->next->data==key)
{
q=p->next;
p->next=NULL;
free(q);
flag=1;
}

return flag;
}

㈣ 链地址法处理冲突的散列表: 试实现用除留余法构造散列表,链地址法处理冲突的散列表类

#include <stdio.h>
#include <malloc.h>

#define NULLKEY 0 // 0为无记录标志
#define N 10 // 数据元素个数

typedef int KeyType;// 设关键字域为整型

typedef struct
{
KeyType key;
int ord;
}ElemType; // 数据元素类型

// 开放寻址哈希表的存储结构
int hashsize[]={11,19,29,37}; // 哈希表容量递增表，一个合适的素数序列
int m=0; // 哈希表表长，全局变量

typedef struct
{
ElemType *elem; // 数据元素存储基址，动态分配数组
int count; // 当前数据元素个数
int sizeindex; // hashsize[sizeindex]为当前容量
}HashTable;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

// 构造一个空的哈希表
int InitHashTable(HashTable *H)
{
int i;
(*H).count=0; // 当前元素个数为0
(*H).sizeindex=0; // 初始存储容量为hashsize[0]
m=hashsize[0];
(*H).elem=(ElemType*)malloc(m*sizeof(ElemType));
if(!(*H).elem)
exit(0); // 存储分配失败
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY; // 未填记录的标志

return 1;
}

// 销毁哈希表H
void DestroyHashTable(HashTable *H)
{
free((*H).elem);
(*H).elem=NULL;
(*H).count=0;
(*H).sizeindex=0;
}

// 一个简单的哈希函数(m为表长，全局变量)
unsigned Hash(KeyType K)
{
return K%m;
}

// 开放寻址法处理冲突
void collision(int *p,int d) // 线性探测再散列
{
*p=(*p+d)%m;
}

// 算法9.17
// 在开放寻址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
// 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS
// c用以计冲突次数，其初值置零，供建表插入时参考。
int SearchHash(HashTable H,KeyType K,int *p,int *c)
{
*p=Hash(K); // 求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
{
// 该位置中填有记录．并且关键字不相等
(*c)++;
if(*c<m)
collision(p,*c); // 求得下一探查地址p
else
break;
}
if (K == H.elem[*p].key)
return SUCCESS; // 查找成功，p返回待查数据元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置
}

int InsertHash(HashTable *,ElemType); // 对函数的声明

// 重建哈希表
void RecreateHashTable(HashTable *H) // 重建哈希表
{
int i,count=(*H).count;
ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i<m;i++) // 保存原有的数据到elem中
if(((*H).elem+i)->key!=NULLKEY) // 该单元有数据
*p++=*((*H).elem+i);
(*H).count=0;
(*H).sizeindex++; // 增大存储容量
m=hashsize[(*H).sizeindex];
p=(ElemType*)realloc((*H).elem,m*sizeof(ElemType));
if(!p)
exit(0); // 存储分配失败
(*H).elem=p;
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY; // 未填记录的标志(初始化)
for(p=elem;p<elem+count;p++) // 将原有的数据按照新的表长插入到重建的哈希表中
InsertHash(H,*p);
}

// 算法9.18
// 查找不成功时插入数据元素e到开放寻址哈希表H中，并返回1；
// 若冲突次数过大，则重建哈希表。
int InsertHash(HashTable *H,ElemType e)
{
int c,p;
c=0;
if(SearchHash(*H,e.key,&p,&c)) // 表中已有与e有相同关键字的元素
return DUPLICATE;
else if(c<hashsize[(*H).sizeindex]/2) // 冲突次数c未达到上限,(c的阀值可调)
{
// 插入e
(*H).elem[p]=e;
++(*H).count;
return 1;
}
else
RecreateHashTable(H); // 重建哈希表

return 0;
}

// 按哈希地址的顺序遍历哈希表
void TraverseHash(HashTable H,void(*Vi)(int,ElemType))
{
int i;
printf("哈希地址0～%d\n",m-1);
for(i=0;i<m;i++)
if(H.elem[i].key!=NULLKEY) // 有数据
Vi(i,H.elem[i]);
}

// 在开放寻址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
// 元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS
int Find(HashTable H,KeyType K,int *p)
{
int c=0;
*p=Hash(K); // 求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
{ // 该位置中填有记录．并且关键字不相等
c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
if (K == H.elem[*p].key)
return SUCCESS; // 查找成功，p返回待查数据元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}

void print(int p,ElemType r)
{
printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}

int main()
{
ElemType r[N] = {
{17,1},{60,2},{29,3},{38,4},{1,5},
{2,6},{3,7},{4,8},{60,9},{13,10}
};
HashTable h;
int i, j, p;
KeyType k;

InitHashTable(&h);
for(i=0;i<N-1;i++)
{
// 插入前N-1个记录
j=InsertHash(&h,r[i]);
if(j==DUPLICATE)
printf("表中已有关键字为%d的记录，无法再插入记录(%d,%d)\n",
r[i].key,r[i].key,r[i].ord);
}
printf("按哈希地址的顺序遍历哈希表:\n");
TraverseHash(h,print);
printf("请输入待查找记录的关键字: ");
scanf("%d",&k);
j=Find(h,k,&p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("没找到\n");
j=InsertHash(&h,r[i]); // 插入第N个记录
if(j==0) // 重建哈希表
j=InsertHash(&h,r[i]); // 重建哈希表后重新插入第N个记录
printf("按哈希地址的顺序遍历重建后的哈希表:\n");
TraverseHash(h,print);
printf("请输入待查找记录的关键字: ");
scanf("%d",&k);
j=Find(h,k,&p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("没找到\n");
DestroyHashTable(&h);

system("pause");
return 0;
}

/*
输出效果：

表中已有关键字为60的记录，无法再插入记录(60,9)
按哈希地址的顺序遍历哈希表:
哈希地址0～10
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=5 (60,2)
address=6 (17,1)
address=7 (29,3)
address=8 (38,4)
请输入待查找记录的关键字: 17
address=6 (17,1)
重建哈希表
按哈希地址的顺序遍历重建后的哈希表:
哈希地址0～18
address=0 (38,4)
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=6 (60,2)
address=10 (29,3)
address=13 (13,10)
address=17 (17,1)
请输入待查找记录的关键字: 13
address=13 (13,10)
请按任意键继续. . .

*/

㈤ 用数据结构链地址法解决冲突，编写插入、删除和查找算法

多看看数据结构里的链接地址法的相关知识，像基本的插入删除，查找都有讲的。看一点树，图的知识。很久没看书了，也忘记了，呵呵。书上有目录的都有联接地址发的叙述的。就是一般的数据结构的书都有吧。主要是在讲二叉树和图的那些地方有这些存储方法的数据结构。

㈥ 如何解决Hash中的冲突问题

1、开放寻址法
用开放寻址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。注意：
①用开放寻址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
按照形成探查序列的方法不同，可将开放寻址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到 T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％m 0≤i≤m-1 //即di=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。 2、拉链法
（1）拉链法解决冲突的方法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：

（2）拉链法的优点
与开放寻址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。

㈦ 哈希查找的解决冲突

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：
(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 = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t * lp = hashTalbe[h];
26:
27: if(lp == NULL)
28: continue;
29: printf([%d] , h);
30: while (lp)
31: {
32: printf( '%s' , lp->u.str)
33: lp = ip->next;
34: }
35: putchar (' ');
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=0;i<m;i++)
{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i].py=;
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i<m;i++)
{
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=0;r<20;r++)
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=0;i<n;i++)
{
cout<<姓名:<<hashlist[i].py<< <<关键字:<<hashlist[i].k<<搜索长度：<<hashlist[i].s<<endl;
}
for(i=0;i<7;i++)
{
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;
}

㈧ 用链表和数组实现HASH表，几种碰撞冲突解决方

1.开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
3.链地址法（拉链法）
将所有关键字为同义词的记录存储在同一线性链表中。
4.建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。