❶ 如何解决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、结构体定义
#ifndef__HASHMAP_H_H_
#define__HASHMAP_H_H_
#includelist.h
#defineTABSIZE101
/*状态变量*/
typedefenumSTATE{EMPTY=0,ACTIVE=1,DELETED=2}State;
/*键值结构体*/
typedefstruct_pair
{
char*key;
char*value;
}Pair_t,*Pair_handle_t;
/*每一个实际的存储对象*/
typedefstruct_hashEntry
{
Pair_handle_tpair;
Statestate;
}HashEntry_t,*HashEntry_handle_t;
/*哈希表结构体，便于创建*/
typedefstruct_hashmap
{
HashEntry_t*map;
/*存储实际的存储量*/
intsize;
/*容量*/
intcapacity;
}Hashmap_t,*Hashmap_handle_t;
/*隐射函数类型定义*/
typedefint(*hashfunc)(constchar*,int);
#ifdef__cplusplus
externC
{
#endif
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity);
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity);
boolinsert_hashnode(Hashmap_handle_thashmap,constchar*key,constchar*value);
Pair_handle_tsearch_hashnode(Hashmap_handle_thashmap,constchar*key);
char*GetValue(Hashmap_handle_thashmap,constchar*key);
booldelete_hashnode(Hashmap_handle_thashmap,constchar*key);
intLength(Hashmap_handle_thashmap);
intCapacity(Hashmap_handle_thashmap);
voiddelete_hashmap(Hashmap_handle_thashmap);
voidfree_hashmap(Hashmap_handle_t*hashmap);
char*key_pair(Pair_handle_tpair);
char*value_pair(Pair_handle_tpair);
Hashmap_handle_t_hashmap(Hashmap_handle_thashmap);
boolresize(Hashmap_handle_thashmap);
#ifdef__cplusplus
}
#endif
#endif
实现表的分配和创建，采用了动态分配的方式实现，这样可能在性能上比不上静态数据，但是为了实现数组大小的调整，我选择了动态分配的实现方式。
/*分配一个新的对象，可以实现自动分配*/
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity)
{
HashEntry_handle_ttemp=NULL;
Hashmap_t*map=NULL;
if(*hashmap==NULL)
{
/*分配一个散列对象*/
map=(Hashmap_handle_t)malloc(sizeof(Hashmap_t));
if(map==NULL)
returnfalse;
/*指针指向当前对象*/
*hashmap=map;
map=NULL;
/*分配一个数组空间，大小可以控制*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
{
/*散列对象的指针指向数组*/
(*hashmap)->map=temp;
temp=NULL;
/*设置参数*/
(*hashmap)->capacity=capacity;
(*hashmap)->size=0;
/*初始化分配的数组空间*/
Tabinital((*hashmap)->map,capacity);
returntrue;
}
}
returnfalse;
}
/*初始化一个新的对象，这个对象已经创建，只是没有初始化而已*/
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity)
{
HashEntry_handle_ttemp=NULL;
if(hashmap!=NULL)
{
/*分配数组空间*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
{
/*完成对象的填充操作*/
hashmap->map=temp;
temp=NULL;
hashmap->capacity=capacity;
hashmap->size=0;
/*初始化数组对象*/
Tabinital(hashmap->map,capacity);
returntrue;
}
}
returnfalse;
}
关于数组中对象的创建，和释放操作，如下所示：
/*分配一个pair对象*/
staticboolmake_pair(Pair_handle_t*pair,constchar*key,constchar*value)
{
Pair_handle_tnewpair=(Pair_handle_t)malloc(sizeof(Pair_t));
char*newstr=NULL;
if(newpair==NULL)
returnfalse;
newstr=(char*)malloc(strlen(key)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,key);
newstr[strlen(key)]=' ';
newpair->key=newstr;
newstr=NULL;
newstr=(char*)malloc(strlen(value)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,value);
newstr[strlen(value)]=' ';
newpair->value=newstr;
newstr=NULL;
(*pair)=newpair;
returntrue;
}
/*释放一个对象pair*/
staticvoiddelete_pair(Pair_handle_t*pair)
{
Pair_handle_ttemp=NULL;
if(*pair==NULL)
return;
temp=*pair;
free(temp->key);
temp->key=NULL;
free(temp->value);
temp->value=NULL;
free(temp);
temp=NULL;
*pair=NULL;
}
数组元素的基本操作：
/*完成数组对象的初始化操作*/
staticvoidTabinital(HashEntry_t*tab,intsize)
{
inti=0;
for(;i
{
tab[i].pair=NULL;
tab[i].state=EMPTY;
}
}
staticvoiddelete_array(HashEntry_handle_t*array,intsize)
{
inti=0;
if(*array!=NULL)
{
for(i=0;i
{
if((*array)[i].state==ACTIVE)
{
delete_pair(&((*array)[i].pair));
(*array)[i].state=DELETED;
}
}
free(*array);
*array=NULL;
}
}
插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。
/*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/
staticboolinsert_data(Hashmap_handle_thashmap,
constchar*key,constchar*value,hashfuncfunc)
{
inthashval=func(key,hashmap->capacity);
intindex=0;
char*newstr=NULL;
Pair_handle_tnewpair=NULL;
while(hashmap->map[hashval].state!=EMPTY)
{
if((hashmap->map[hashval].state==ACTIVE)
&&(strcmp(hashmap->map[hashval].pair->key,key)==0))
break;
index++;
hashval+=index*index;
hashval%=hashmap->capacity;
if(index==200)
break;
}
if(hashmap->map[hashval].state==EMPTY)
{
if(make_pair(&newpair,key,value))
{
hashmap->map[hashval].state=ACTIVE;
hashmap->map[hashval].pair=newpair;
newpair=NULL;
hashmap->size++;
returntrue;
}
数据在计算机中存储的物理结构有四种：顺序、链表、散列与索引。散列是由单词Hash翻译过来的，有时也直接音译为“哈希”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
❹ C语言 数据结构中解决冲突的方法是什么
可以参考如下方法：
1 基本原理
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接寻址"与"解决冲突"是哈希表的两大特点。
2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的
end;
查找元素是否已经在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。
4.1 应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问："某个元素是否在已知集合中？"，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用"除余法"的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。
简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 则有 q mod p= q - p* [q div p] =q - p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住"素数是我们的得力助手"。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而"好"的标准，就是较低的冲突率和易于实现。