• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0

            這是第一種哈希函數(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;
            }
            這是用書中提到的ELFhash()函數(shù),也沒體現(xiàn)出時間上的優(yōu)勢,但空間上確實是省了不少,可能是計算ELFhash()時浪費了時間吧,處理字符串哈希沖突的辦法目前只發(fā)現(xiàn)了線形探測法,雖然不理想,但愿將來能發(fā)現(xiàn)別的辦法。
            ELFhash函數(shù)在UNIX系統(tǒng)V 版本4中的“可執(zhí)行鏈接格式”( Executable and Linking Format,即ELF )中會用到,ELF文件格式用于存儲可執(zhí)行文件與目標(biāo)文件。ELFhash函數(shù)是對字符串的散列。它對于長字符串和短字符串都很有效,字符串中每個字符都 有同樣的作用,它巧妙地對字符的ASCII編碼值進(jìn)行計算,ELFhash函數(shù)對于能夠比較均勻地把字符串分布在散列表中。
            #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博客,轉(zhuǎn)載請標(biāo)明出處:http://blog.csdn.net/cugbliang/archive/2008/05/30/2497539.aspx

            posted on 2009-07-01 14:29 luis 閱讀(937) 評論(0)  編輯 收藏 引用 所屬分類: 轉(zhuǎn)載
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久高清一级毛片| 免费精品国产日韩热久久| 久久精品亚洲日本波多野结衣| 无遮挡粉嫩小泬久久久久久久| 99久久超碰中文字幕伊人| 亚洲欧美日韩精品久久| 久久笫一福利免费导航| 97久久精品国产精品青草| 久久精品综合一区二区三区| 少妇久久久久久久久久| 久久高清一级毛片| 久久99国产精品久久久| 国产激情久久久久久熟女老人| 青青青国产精品国产精品久久久久| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区| 一本大道久久东京热无码AV | 久久久久久国产精品无码下载| 一本一本久久a久久精品综合麻豆| 91精品国产高清久久久久久io| 亚洲欧洲久久久精品| 国产精品美女久久久久av爽| 久久国产乱子伦免费精品| 国产69精品久久久久APP下载| 93精91精品国产综合久久香蕉| 久久久久久国产精品免费无码| 一本一道久久a久久精品综合| 人妻中文久久久久| 久久久久亚洲精品男人的天堂| 久久免费精品一区二区| 国产精品久久久久久| 丰满少妇人妻久久久久久| 日韩精品无码久久久久久| 香蕉久久永久视频| 久久伊人亚洲AV无码网站| 国产精品无码久久四虎| 久久国产影院| 久久91精品国产91| 18岁日韩内射颜射午夜久久成人| 合区精品久久久中文字幕一区| 久久免费观看视频| 东方aⅴ免费观看久久av|