锐客网

  1. 首页 > it技术 > >

hash散列表链表冲突

总所周知，利用哈希散列能很快的找到你数据存储的地方，减少索引时的时间复杂度，但是你使用的哈希算法，数据量一大就会有冲突问题，是用哈希最头疼的问题。
那么：
冲突是如何产生的？
【hash散列表链表冲突】上文中谈到，哈希函数是指如何对关键字进行编址的规则，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？
如何解决冲突问题
既然不能避免冲突，那么如何解决冲突呢，显然需要附加的步骤。通过这些步骤，以制定更多的规则来管理关键字集合，通常的办法有:
a)开放地址法
开放地执法有一个公式: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取值可能为伪随机数列。称伪随机探测再散列。

b)再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止。



c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。

下面就取一个链地址法的解决方案。
#include
#include
#include
#defineSIZE 10


//链表节点
typedef struct node
{
int data;
struct node* next;
}node;


//hash表的元素结构
//first:链表首地址
//last:链表最后一个节点地址
//这样当我有新的节点要来时,我就不用每次从第一个节点开始搜索判断,直接放到last后面
typedef struct block
{
node *first;
node* last;
}block;


//初始化hash表
voidinithashtable(block* hashtable[])
{
int i;
for(i=0; i{
hashtable[i]=NULL;
}
}


//存储数据并用链表法解决冲突问题
void savehashtable(block* hashtable[])
{
int i=0;
int j=0;
int data;
srand((time_t)time(NULL));
for(i=0; i<100; i++)//模仿多个数据(随机生成100个2位整数)
{
data=https://www.it610.com/article/rand()%100;
printf("%d\t",data);
node * newnode=(node*)malloc(1*sizeof(node));
while(newnode==NULL)
{
newnode=(node*)malloc(1*sizeof(node));
}
newnode->data=https://www.it610.com/article/data;
newnode->next=NULL;



if(hashtable[data%10]==NULL)
{
block* bp;
bp=(block*)malloc(1*sizeof(block));
while(bp==NULL)
{
bp=(block*)malloc(1*sizeof(block));
}
bp->first=newnode;
bp->last=newnode;
newnode=NULL;


hashtable[data%10]=bp;
}
else
{
block* tmp=hashtable[data%10];
tmp->last->next=newnode;
tmp->last=newnode;
newnode=NULL;
}
}
}


//查找hash表
void queryhashtable(block* hashtable[],intdata)
{
int flag=0;
block* bh=hashtable[data%10];
if(bh!=NULL)
{
node * curr;
for(curr=bh->first; curr!=bh->last; curr=curr->next)
{
if(curr->data=https://www.it610.com/article/=data)
{
flag=1;
printf("%d find\n",data);
}
}
}
if(flag==0)
{
printf("%d not find\n",data);
}
}


int main(int argc, char const *argv[])
{
block * hashtable[SIZE];
inithashtable(hashtable);
savehashtable(hashtable);
//测试代码
printf("\n");
int data;
scanf("%d",&data);
queryhashtable(hashtable,data);
return 0;
}



这是我学习中的心得，希望对大家能有帮助。


    推荐阅读


    上一篇：S3C6410系统时钟

    下一篇：前端生成UUId