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

            牽著老婆滿街逛

            嚴(yán)以律己,寬以待人. 三思而后行.
            GMail/GTalk: yanglinbo#google.com;
            MSN/Email: tx7do#yahoo.com.cn;
            QQ: 3 0 3 3 9 6 9 2 0 .

            time33 哈希函數(shù),又叫 DJBX33A,Bernstein's hash

            轉(zhuǎn)載自:http://www.cnblogs.com/napoleon_liu/articles/1911571.html

            php, apache, perl, bsddb都使用time33哈希.

            最簡(jiǎn)單的版本

              uint32_t time33(char const *str, int len) 
                

                    unsigned 
            long  hash = 0
                    
            for (int i = 0; i < len; i++
                        hash 
            = hash *33 + (unsigned long) str[i]; 
                    }
             
                    
            return hash; 
                }

             

            這個(gè)版本最可以體現(xiàn)time33的算法思路,夠簡(jiǎn)單。

             

            把乘法操作換成位操作

                    unsigned long time33(char const *str, int len) 
                

                    unsigned 
            long  hash = 0
                    
            for (int i = 0; i < len; i++
                        hash 
            = ((hash <<5+ hash) + (unsigned long) str[i]; 
                    }
             
                    
            return hash; 
                }
             

            59個(gè)字符1000 0000次運(yùn)行(gcc沒(méi)有開(kāi)啟優(yōu)化,因?yàn)殚_(kāi)了優(yōu)化后兩個(gè)函數(shù)的實(shí)際代碼會(huì)一樣)

            第一個(gè):

            real    0m4.389s 
            user    0m4.388s 
            sys     0m0.000s

             

            第二個(gè):

            real    0m4.137s 
            user    0m4.120s 
            sys     0m0.000s

             

             

            gcc –O2優(yōu)化后是

            real    0m1.367s 
            user    0m1.360s 
            sys     0m0.000s

             

             

            php版本

             

            inline unsigned time33(char const*str, int len) 

                 unsigned long hash 
            = 5381
                 
            /* variant with the hash unrolled eight times */ 
                 
            for (; len >= 8; len -= 8) { 
                     hash 
            = ((hash << 5+ hash) + *str++
                     hash 
            = ((hash << 5+ hash) + *str++
                     hash 
            = ((hash << 5+ hash) + *str++
                     hash 
            = ((hash << 5+ hash) + *str++
                    hash 
            = ((hash << 5+ hash) + *str++
                    hash 
            = ((hash << 5+ hash) + *str++
                    hash 
            = ((hash << 5+ hash) + *str++
                    hash 
            = ((hash << 5+ hash) + *str++
                } 
                
            switch (len) { 
                    
            case 7: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 6: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 5: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 4: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 3: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 2: hash = ((hash << 5+ hash) + *str++/* fallthrough */ 
                    
            case 1: hash = ((hash << 5+ hash) + *str++break
                    
            case 0: break
                } 
                
            return hash; 

             

            59個(gè)字符,1000 0000次

            real    0m1.088s 
            user    0m1.068s 
            sys     0m0.000s

             

            速度提升主要在循環(huán)展開(kāi), 對(duì)于短字符,這個(gè)是不明顯的。

            php版本的hash初始值是5381, 這個(gè)

             

            Magic Constant 5381:

              
            1. odd number

              
            2. prime number

              
            3. deficient number

              
            4001/010/100/000/101 b

             

            Apache版本

            unsigned long time33(char const  *str, int *len) 

                unsigned 
            long hash = 0;

                
            const char *p=str; 
                
            if (*len<=0
                    
            for(p = str; *p; p++
                        hash 
            = hash * 33 + *p; 
                    }
             
                    
            *len = p - str; 
                }
             
                
            else 
                    
            int i = *len; 
                    
            for (p = str;i; i--, p++
                        hash 
            = hash * 33 + *p; 
                    }
             
                }
             
                
            return hash; 
            }

             

            測(cè)試結(jié)果

            real    0m1.418s 
            user    0m1.412s 
            sys     0m0.004s

             

             

            綜上,我的改進(jìn)版本

            #define likely(x) __builtin_expect((x),1) 
            #define unlikely(x) __builtin_expect((x),0) 
                
            //php版本 
                unsigned long time33(char const *str, int len=-1
                

                    unsigned 
            long hash = 5381
                    
            /* variant with the hash unrolled eight times */ 
                    
            char const *= str; 
                    
            if (unlikely(len<0)) 
                            
            for(; *p; p++
                                hash 
            = hash * 33 + *p; 
                            }
             
                            
            return hash; 
                    }


            #define TIME33_HASH_MIXED_CH()  hash = ((hash<<5)+hash) + *p++ 
                    
            for (; len >= 8; len -= 8
                        TIME33_HASH_MIXED_CH(); 
            //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                        TIME33_HASH_MIXED_CH(); //
                   }
             
                   
            switch (len) 
                       
            case 7: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 6: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 5: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 4: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 3: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 2: TIME33_HASH_MIXED_CH(); /* fallthrough */ 
                       
            case 1: TIME33_HASH_MIXED_CH(); break
                       
            case 0break
                   }
             
                   
            return hash; 
               }


            #undef TIME33_HASH_MIXED_CH

             

            測(cè)試結(jié)果

            real    0m1.072s 
            user    0m1.064s 
            sys     0m0.000s

            測(cè)試過(guò), 重復(fù)率在 1/2000。

             

            為什么是33的倍數(shù), PHP中注釋是

            DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
              This 
            is Daniel J. Bernstein's popular `times 33' hash function as
              posted by him years ago on comp.lang.c. It basically uses a function
              like ``hash(i) 
            = hash(i-1* 33 + str[i]''. This is one of the best
              known hash functions 
            for strings. Because it is both computed very
              fast and distributes very well.
              The magic of number 
            33, i.e. why it works better than many other
              constants, prime or not, has never been adequately explained by
              anyone. So I 
            try an explanation: if one experimentally tests all
              multipliers between 
            1 and 256 (as RSE did now) one detects that even
              numbers are not useable at all. The remaining 
            128 odd numbers
              (except 
            for the number 1) work more or less all equally well. They
              all distribute 
            in an acceptable way and this way fill a hash table
              with an average percent of approx. 
            86%.
              If one compares the Chi
            ^2 values of the variants, the number 33 not
              even has the best value. But the number 
            33 and a few other equally
              good numbers like 
            173163127 and 129 have nevertheless a great
              advantage to the remaining numbers 
            in the large set of possible
              multipliers: their multiply operation can be replaced by a faster
              operation based on just one shift plus either a single addition
              or subtraction operation. And because a hash function has to both
              distribute good _and_ has to be very fast to compute, those few
              numbers should be preferred and seems to be the reason why Daniel J.
              Bernstein also preferred it.
                               
            -- Ralf S. Engelschall rse@engelschall.com

             

             

            其它倍數(shù)

            Ngix使用的是 time31

            Tokyo Cabinet使用的是 time37

            Bob在他的文章說(shuō),小寫(xiě)英文詞匯適合33, 大小寫(xiě)混合使用65。time33比較適合的是英文詞匯的hash.


            posted on 2011-07-26 15:07 楊粼波 閱讀(1936) 評(píng)論(0)  編輯 收藏 引用


            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            国产成人无码精品久久久免费 | 国产精品免费久久久久影院 | 99热都是精品久久久久久| 99久久精品无码一区二区毛片 | 丁香色欲久久久久久综合网| 久久这里有精品| 久久A级毛片免费观看| 久久久噜噜噜久久中文福利| 久久99国产精品久久久| 亚洲中文字幕伊人久久无码 | 久久精品国产亚洲麻豆| 一本大道久久东京热无码AV| 日韩精品无码久久久久久| 精品免费久久久久国产一区| 久久午夜无码鲁丝片| 欧美久久一级内射wwwwww.| 狠狠色丁香婷综合久久| 久久婷婷五月综合国产尤物app| 久久精品国内一区二区三区 | 久久成人国产精品免费软件| 久久久久久狠狠丁香| 亚洲精品乱码久久久久久蜜桃不卡| 国产福利电影一区二区三区久久久久成人精品综合 | 国产精品美女久久久网AV| 无码久久精品国产亚洲Av影片| 国产成人精品久久亚洲| 久久久久久国产精品免费无码| 日本五月天婷久久网站| 久久久噜噜噜久久中文字幕色伊伊| 69国产成人综合久久精品| AV狠狠色丁香婷婷综合久久| 亚洲精品tv久久久久| 久久无码AV中文出轨人妻| 夜夜亚洲天天久久| 久久噜噜电影你懂的| 好属妞这里只有精品久久| 国产99精品久久| 国产精品VIDEOSSEX久久发布| 99热成人精品热久久669| 久久精品国产亚洲AV无码娇色| 亚洲AV无码1区2区久久|