• <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精品成人片中文字幕| 久久综合狠狠综合久久97色| 久久人人青草97香蕉| 一级a性色生活片久久无| 久久国产精品99国产精| 国产福利电影一区二区三区久久久久成人精品综合 | 久久99国产精品久久99| 国内精品久久久久影院网站| 久久精品国产亚洲AV蜜臀色欲 | 欧美午夜A∨大片久久| 久久天天躁狠狠躁夜夜躁2O2O| 青青青青久久精品国产h久久精品五福影院1421 | 思思久久精品在热线热| 91久久国产视频| 97久久精品午夜一区二区| 久久久久久久女国产乱让韩| 99久久国产热无码精品免费| 97久久婷婷五月综合色d啪蜜芽| 婷婷久久综合九色综合98| 麻豆久久久9性大片| 99久久无码一区人妻a黑| 久久男人中文字幕资源站| 久久久精品2019免费观看| 久久丝袜精品中文字幕| 99久久成人国产精品免费 | 久久国产热精品波多野结衣AV| 欧美久久亚洲精品| 99久久国产综合精品成人影院| 亚洲精品无码久久一线| 合区精品久久久中文字幕一区| 99久久人人爽亚洲精品美女| 少妇久久久久久久久久| 亚洲国产精品无码久久久久久曰 | 久久九九免费高清视频| 国产激情久久久久影院老熟女| 99久久精品午夜一区二区| 精品久久久中文字幕人妻| 亚洲日本va午夜中文字幕久久| 久久久亚洲精品蜜桃臀| 久久精品成人免费国产片小草|