哈希Hash

     要点一：哈希表长度 的确定是个两难的问题：太短则容易造成冲突(POJ->TLE)；太长则浪费存储空间(POJ->MLE)。另外，有兴趣看一下“最小完美哈希函数”

     要点二：哈希冲突 是必须解决的问题，主要有一下几种解决方案

                （1）开放定址法 ：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。

                （2）链地址法 ：将所有关键字相同的节点链接在同一个单链表中。

                （3）再哈希法 ：当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突

                （4）建立一个公共溢出区 ：假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

 

     其实这个东西很简单，主要要熟悉实现方法。下面直接上几个例题：

 

注：代码中尚未解决hash溢出问题!!!

 

POJ 2503 Babelfish ==>  http://poj.org/problem?id=2503

C++代码（开放地址，线性探查 ）

//poj 2503 Babelfish 

#include <iostream>        //ELFhash函数是对字符串的散列
#include <string>
using namespace std;
#define M 1000000
//M如果较小则不能很好地避免冲突，解决冲突需要更多的时间，会TLE,比如200000 当然不能过大，会MLE，比如10000000
//M取适合的值，既可以避免hash开得太大，同时又可以减少冲突 
string hash[M],res[M];
int ELFHash(string str)        //ELFhash函数
{
    int h = 0;
    int x  = 0;
    for(int i=0;i<str.size();++i)
    {
        h = (h << 4) + (str[i]);
        if ((x = h & 0xF0000000L) != 0)
        {
            h ^= (x >> 24);
            h &= ~x;
        }
    }
    return h % M;
}

int main()
{

    string str,e,f,s;
    int ind;
    while(getline(cin,str))     //如果输入某行是“直接回车”的话，则str=""，while("")导致退出循环
    {
        if(str.size()==0)
            break;
        int pos=str.find(' ');
        e.assign(str,0,pos);    //添加从下标[0]开始的pos个字符
        f.assign(str,pos+1,str.size()-1-pos);    
        
        ind=ELFHash(f);
        while(hash[ind]!="")
            ind=(ind+1)%M;
        hash[ind]=f;
        res[ind]=e;
    }
    while(cin>>s)
    {
        ind=ELFHash(s);
        if(hash[ind]=="")
            cout<<"eh\n";    
        else
        {
            while(hash[ind]!=s && hash[ind]!="")
                ind=(ind+1)%M;        //开放地址法 线性探查法
            if(res[ind]!=""){
                cout<<res[ind]<<endl;
            }else{
                cout<<"eh\n";
            }
        }
    }
    return 0;
}

 

C++代码： （链地址法 ）

#include <iostream>
#include <fstream>
#include <string.h>

#define N 100001
#define strSize 15

using namespace std;

struct hash{
    bool used;
    char fn[strSize],en[strSize];
    hash* next;    //用于冲突时构造链表
        hash(){used=false; next=NULL;}
        hash(char *f,char *e)
    {
        strcpy(fn,f);
        strcpy(en,e);
        used=false;
        next=NULL;
    }    
}h[N];

int ELFhash(char *key){

    unsigned long h=0;
    unsigned long x=0;

    while(*key)
    {
        h=(h<<4)+(*key++);  //h左移4位，当前字符ASCII存入h的低四位
                if( (x=h & 0xF0000000L)!=0)
        { //如果最高位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出
          //因此要有如下处理
          h^=(x>>24);
          //清空28~31位
          h&=~x;
        }
    }
    return h % N;
}


int main()
{
    freopen("acm.txt","r",stdin);
    char str[30],en[strSize],fn[strSize];
    hash* p;
    int sign=1,key;

    while(gets(str))
    {
        if(str[0]=='\0')
        {
            sign=0;
            continue;
        }
        if(sign)   //输入字典
        {
            sscanf(str,"%s %s",&en,&fn);
            key=ELFhash(fn);    //获取hash值
            if(!h[key].used)    //对应到hash表中
            {
                h[key].used=true;
                strcpy(h[key].en,en);
                strcpy(h[key].fn,fn);
            }
            else   //处理冲突
            {
                p=&h[key];
                while(p->next != NULL) p=p->next;
                p->next=new hash(fn,en);
            }

        }
        else  //输入外文
        {
            key=ELFhash(str);
            if(!h[key].used) printf("eh\n");
            else
            {
                p=&h[key];
                while(p!=NULL)
                {
                    if(!strcmp(str,p->fn))
                    {
                        printf("%s\n",p->en);
                        break;
                    }
                    else
                    {
                        p=p->next;
                    }
                }
                if(p==NULL) printf("eh\n");  //不匹配的情况，不能少
            }
        
        }

    }
    return 0;
}