这是第一种哈希函数，运行时间短，但内存占用多。哈希函数是怎么得到的？我也想知道。。。
#include<stdio.h>
#include<string.h>
#include<math.h>
struct abc
{
    int boo;
    char key[12];
}hash[1100005];
int const prime=999983;
double const gold=0.618033;
void insert(char a[],int k,int w)
{
    if(hash[w].boo==0)
    {   
        hash[w].boo=k;
        memcpy(hash[w].key,a,sizeof(hash[w].key));
    }
    else
        insert(a,k,w%prime+1);    
}
int find(int k,int w)
{
    if(hash[w].boo==k)
    {
        printf("%s\n",hash[w].key);
            return 1;
    }   
    else
    {
        if(hash[w].boo==0)
            return 0;
        else
            return find(k,w%prime+1);
    }   
}
int main()
{
    freopen("in.txt","r",stdin);
    char a[12],b[12];
    scanf("%c",&a[0]);
    while(scanf("%s%s",a+1,b))
    {
        getchar();
        int len=strlen(b);
        int k=0;
        for(int i=0;i<len;i++)
            k=k*26+b[i]-'a';
        int w=int (prime*(k*gold-floor(k*gold)));
        insert(a,k,w);
        scanf("%c",&a[0]);
        if(a[0]=='\n')
            break;
    }
    while(scanf("%s",&a)==1)
    {
        int len=strlen(a);
        int k=0;
        for(int i=0;i<len;i++)
        k=k*26+a[i]-'a';
        int w=int (prime*(k*gold-floor(k*gold)));
        if(find(k,w)==0)
        printf("eh\n");
    }
    return 0;
}
这是用书中提到的ELFhash()函数，也没体现出时间上的优势，但空间上确实是省了不少，可能是计算ELFhash()时浪费了时间吧，处理字符串哈希冲突的办法目前只发现了线形探测法，虽然不理想，但愿将来能发现别的办法。
ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format，即ELF )中会用到，ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效，字符串中每个字符都 有同样的作用，它巧妙地对字符的ASCII编码值进行计算，ELFhash函数对于能够比较均匀地把字符串分布在散列表中。
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MOD 300005
struct abc
{
    bool boo;
    char akey[12];
    char bkey[12];
}hash[300005];

int ELFhash(char *key)
{
    unsigned long h=0;
    while(*key)
    {
        h=(h<<4)+*key++;
        unsigned long g=h&0Xf0000000L;
        if(g) h^=g>>24;
        h&=~g;
    }
    return h%MOD;
}
void insert(char a[],char b[],int w)
{
    if(!hash[w].boo)
    {   
        hash[w].boo=true;
        memcpy(hash[w].akey,a,sizeof(hash[w].akey));
        memcpy(hash[w].bkey,b,sizeof(hash[w].bkey));
    }
    else
        insert(a,b,w+1);    
}
int find(char b[],int w)
{
    if(hash[w].boo && strcmp(hash[w].bkey,b)==0)
    {
        printf("%s\n",hash[w].akey);
            return 1;
    }   
    else
    {
        if(!hash[w].boo)
            return 0;
        else
            return find(b,w+1);
    }   
}
int main()
{
    char a[12],b[12];
    scanf("%c",&a[0]);
    while(scanf("%s%s",a+1,b))
    {
        getchar();
        int w=ELFhash(b);
        insert(a,b,w);
        scanf("%c",&a[0]);
        if(a[0]=='\n')
            break;
    }
    while(scanf("%s",&b)==1)
    {
        int w=ELFhash(b);
        if(find(b,w)==0)
        printf("eh\n");
    }
    return 0;
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/cugbliang/archive/2008/05/30/2497539.aspx