首页 > 代码库 > 【模版】简单哈希和哈希表处理冲突

【模版】简单哈希和哈希表处理冲突

2024-07-18 00:39:10   226人阅读

哈希（Hash）算法就是单向散列算法，它把某个较大的集合P映射到另一个较小的集合Q中。数学原理听起来很抽象，在网上找到一个很生动的描述。我们有很多的小猪，每个的体重都不一样，假设体重分布比较平均(我们考虑到公斤级别)，我们按照体重来分,划分成100个小猪圈。 然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。如果我们要精确找到某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？ 当然不需要了。 我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。

当题目中数值很小的时候我们只需要用哈希数组来存取数值来当作它的下标，从而寻找

http://blog.csdn.net/u013486414/article/details/30775765 这道题可以让你明白简单哈希的应用。

当数值特别大的时候我们运用哈希表，哈希表存储的时候可能会有一个地址出现两个数值，以为一个地址只能有一个数值的储存，所以这就产生了冲突，冲突的处理方法有好多种，我一般用链表处理，这也是当初学长交给我的，先挂后找。

例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13,
   用链地址法处理冲突：



先把他们用链表存起来，然后找。

struct node  
{  
    int date;  
    struct node *next;  
}*h[N];  
void gua (int x)  //先把链表挂上
{  
    int a=x%N;  
    struct node *p;  
    p=(struct node *)malloc(sizeof(struct node ));  
    p->date=x;  
    p->next=h[a];  
    h[a]=p;  
}  
int findx (int x)  //再寻找
{  
    int a = x%N;  
    int count  = 0;  
    for (struct node *p = h[a]; p; p = p->next)  
    {  
        if (p->date == x)   
            count ++;  
    }  
    return count ;  
}

http://blog.csdn.net/u013486414/article/details/30826753  这道题可以好好看一下


联系
我们