這是第一種哈希函數(shù)，運(yùn)行時(shí)間短，但內(nèi)存占用多。哈希函數(shù)是怎么得到的？我也想知道。。。
#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;
}
這是用書(shū)中提到的ELFhash()函數(shù)，也沒(méi)體現(xiàn)出時(shí)間上的優(yōu)勢(shì)，但空間上確實(shí)是省了不少，可能是計(jì)算ELFhash()時(shí)浪費(fèi)了時(shí)間吧，處理字符串哈希沖突的辦法目前只發(fā)現(xiàn)了線形探測(cè)法，雖然不理想，但愿將來(lái)能發(fā)現(xiàn)別的辦法。
ELFhash函數(shù)在UNIX系統(tǒng)V 版本4中的“可執(zhí)行鏈接格式”( Executable and Linking Format，即ELF )中會(huì)用到，ELF文件格式用于存儲(chǔ)可執(zhí)行文件與目標(biāo)文件。ELFhash函數(shù)是對(duì)字符串的散列。它對(duì)于長(zhǎng)字符串和短字符串都很有效，字符串中每個(gè)字符都 有同樣的作用，它巧妙地對(duì)字符的ASCII編碼值進(jìn)行計(jì)算，ELFhash函數(shù)對(duì)于能夠比較均勻地把字符串分布在散列表中。
#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;
}

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/cugbliang/archive/2008/05/30/2497539.aspx