• <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

            這是第一種哈希函數,運行時間短,但內存占用多。哈希函數是怎么得到的?我也想知道。。。
            #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

            posted on 2009-07-01 14:29 luis 閱讀(937) 評論(0)  編輯 收藏 引用 所屬分類: 轉載
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            91精品国产9l久久久久| 中文字幕精品无码久久久久久3D日动漫| 国产精品一久久香蕉国产线看| 91精品国产91久久久久福利| 久久精品www| 一级女性全黄久久生活片免费 | 亚洲人成精品久久久久| 青青草原综合久久大伊人导航| 国产精品久久久久a影院| 久久男人Av资源网站无码软件| AAA级久久久精品无码片| 国产精品欧美亚洲韩国日本久久 | 77777亚洲午夜久久多人| 久久99精品国产麻豆宅宅| 亚洲国产精品无码久久久久久曰 | 国内精品久久久久久麻豆 | 久久人人青草97香蕉| 精品久久久久久国产| 久久无码AV一区二区三区| 久久99国产精品久久99果冻传媒| 久久这里的只有是精品23| 国产精品综合久久第一页 | 草草久久久无码国产专区| 亚洲中文字幕无码一久久区| 久久亚洲中文字幕精品一区| 久久99精品久久久久子伦| 中文字幕热久久久久久久| 亚洲国产成人久久综合碰| 色综合久久综合网观看| 91精品国产9l久久久久| 精品国产一区二区三区久久久狼 | 精品国产乱码久久久久久1区2区 | 国产成人无码精品久久久性色| 久久伊人中文无码| 国产无套内射久久久国产| 久久午夜电影网| 色噜噜狠狠先锋影音久久| 99久久精品国内| 2020久久精品国产免费| 亚洲精品高清国产一久久| 精品久久久久久无码人妻热|