哈希函数的构造方法常用的有5种,分别是数字分析法,平方取中法,分段叠加,伪随机数法和余数法,其中余数法比较常用

虽然通过构造好的哈希函数可以减少冲突,但冲突是不可能完全避免的,所以就相应的产生了避免哈希冲突的4种方法,分别是开放定址法(包括线性探测再散列和二次探测再散列),链地址法,再哈希法和建立公共溢出区

 

开放定址法中的线性探测再散列比较常用,该方法的特点是在冲突发生时,顺序查看表中的下一单元,直到找出一个空单元或遍历全表

#include <stdio.h>
#include <time.h>

#define Max 11
#define N 8
int hashtable[Max];

int func(int value)
{
        return value%Max;
}

int search(int key)
{
        int pos,t;
        pos = func(key);
        t = pos;

        while(hashtable[t] != key && hashtable[t] != -1)
        {
                t = func(t+1);
                if(pos == t) return -1;
        }
        if(hashtable[t] == -1) return 0;
        return t;
}

void createhash(int key)
{
        int pos,t;
        pos = func(key);
        t = pos;
        while(hashtable[t] != -1)
        {
                t = func(t+1);
                if(pos == t) return;
        }
        hashtable[t] = key;
}

int main(void)
{
        int arr[50];
        int i,j,t;

        for(i = 0;i<Max;i++)
        {
                hashtable[i] = -1;
        }

        for(i=0;i<50;i++)
        {
                arr[i] = i;
                createhash(i);
        }

        scanf("%d",&t);

        i = search(t);

        printf("%d",i);

        return 0;
}