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

            無我

            讓內心永遠燃燒著偉大的光明的精神之火!
            靈活的思考,嚴謹的實現
            豪邁的氣魄、頑強的意志和周全的思考

            hash函數——djb2、sdbm、lose lose

            本文內容轉自于http://www.cse.yorku.ca/~oz/hash.html。因為他對給出了幾個非常好的hash函數,而其中的sdbm就是我們將剖析的eSNACC用的hash的原型。文章是英文的,但是通俗易懂,就摘錄在此了。

             

            Hash Functions

            A comprehensive collection of hash functions, a hash visualiser and some test results [see Mckenzie et al. Selecting a Hashing Algorithm, SP&E 20(2):209-224, Feb 1990] will be available someday. If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes. you are not likely to do better with one of the "well known" functions such as PJW, K&R[1], etc. Also see tpop pp. 126 for graphing hash functions.


             

            djb2

            this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.

                unsigned long
                hash(unsigned char *str)
                {
                    unsigned long hash = 5381;
                    int c;
            
                    while (c = *str++)
                        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
            
                    return hash;
                }
            


             

            sdbm

            this algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library. it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits. it also happens to be a good general hashing function with good distribution. the actual function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below is the faster version used in gawk. [there is even a faster, duff-device version] the magic constant 65599 was picked out of thin air while experimenting with different constants, and turns out to be a prime. this is one of the algorithms used in berkeley db (see sleepycat) and elsewhere.

                static unsigned long
                sdbm(str)
                unsigned char *str;
                {
                    unsigned long hash = 0;
                    int c;
            
                    while (c = *str++)
                        hash = c + (hash << 6) + (hash << 16) - hash;
            
                    return hash;
                }

            lose lose

            This hash function appeared in K&R (1st ed) but at least the reader was warned: "This is not the best possible algorithm, but it has the merit of extreme simplicity." This is an understatement; It is a terrible hashing algorithm, and it could have been much better without sacrificing its "extreme simplicity." [see the second edition!] Many C programmers use this function without actually testing it, or checking something like Knuth's Sorting and Searching, so it stuck. It is now found mixed with otherwise respectable code, eg. cnews. sigh. [see also: tpop]

                unsigned long
                hash(unsigned char *str)
                {
            	unsigned int hash = 0;
            	int c;
            
            	while (c = *str++)
            	    hash += c;
            
            	return hash;
                }
            

             

             

            posted on 2012-04-26 08:52 Tim 閱讀(2644) 評論(1)  編輯 收藏 引用 所屬分類: C/C++語言

            評論

            # re: hash函數——djb2、sdbm、lose lose[未登錄] 2012-04-27 09:35 Tina

            頂!  回復  更多評論   

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            公告

            本博客原創文章,歡迎轉載和交流。不過請注明以下信息:
            作者:TimWu
            郵箱:timfly@yeah.net
            來源:www.shnenglu.com/Tim
            感謝您對我的支持!

            留言簿(9)

            隨筆分類(173)

            IT

            Life

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            麻豆一区二区99久久久久| 99久久精品国产综合一区| 尹人香蕉久久99天天拍| 亚洲精品无码专区久久久| 成人久久综合网| 久久国产免费直播| 精品久久久无码人妻中文字幕| 72种姿势欧美久久久久大黄蕉| 久久99精品国产麻豆不卡| 久久狠狠爱亚洲综合影院| 久久99久久99小草精品免视看 | 精品国产VA久久久久久久冰| 国产午夜精品理论片久久| 狠狠综合久久综合88亚洲| 国产精品久久久久9999| 7777精品久久久大香线蕉| 99久久99久久精品国产片| 久久久久高潮毛片免费全部播放| 国内精品伊人久久久久网站| 久久久久99精品成人片欧美| 香蕉久久永久视频| 天堂无码久久综合东京热| 国产精品成人无码久久久久久 | 韩国免费A级毛片久久| 午夜精品久久久久| 欧美久久一区二区三区| 国内精品久久久久久久涩爱 | 久久99热这里只频精品6| 国产精品激情综合久久| 国产精品欧美久久久天天影视| 亚洲精品无码久久久影院相关影片| 无码8090精品久久一区| 亚洲人AV永久一区二区三区久久| 91久久香蕉国产熟女线看| 婷婷综合久久中文字幕| 欧美综合天天夜夜久久| 中文字幕亚洲综合久久| 精品无码人妻久久久久久| 久久久久国产亚洲AV麻豆| 久久影院午夜理论片无码| 久久久久久青草大香综合精品 |