復(fù)制代碼 代碼如下:
APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
                                                      apr_ssize_t *klen)
{
    unsigned int hash = 0;
    const unsigned char *key = (const unsigned char *)char_key;
    const unsigned char *p;
    apr_ssize_t i;

    /*
     * This is the popular `times 33' hash algorithm which is used by
     * perl and also appears in Berkeley DB. This is one of the best
     * known hash functions for strings because it is both computed
     * very fast and distributes very well.
     *
     * The originator may be Dan Bernstein but the code in Berkeley DB
     * cites Chris Torek as the source. The best citation I have found
     * is "Chris Torek, Hash function for text in C, UseNET message
     * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
     * Salz's USENIX 1992 paper about INN which can be found at
     * .
     *
     * 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 I did while writing a low-level
     * data structure library some time ago) 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 (see
     * Bob Jenkins ``Hashing Frequently Asked Questions'' at
     * http://burtleburtle.NET/bob/hash/hashfaq.html for a description
     * of chi^2), the number 33 not even has the best value. But the
     * number 33 and a few other equally good numbers like 17, 31, 63,
     * 127 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.
     *
     *                  -- Ralf S. Engelschall
     */

    if (*klen == APR_HASH_KEY_STRING) {
        for (p = key; *p; p++) {
            hash = hash * 33 + *p;
        }
        *klen = p - key;
    }
    else {
        for (p = key, i = *klen; i; i--, p++) {
            hash = hash * 33 + *p;
        }
    }
    return hash;
}

對函數(shù)注釋部分的翻譯: 這是很出名的times33哈希算法,此算法被perl語言采用并在Berkeley DB中出現(xiàn).它是已知的最好的哈希算法之一,在處理以字符串為鍵值的哈希時(shí),有著極快的計(jì)算效率和很好哈希分布.最早提出這個(gè)算法的是Dan Bernstein,但是源代碼確實(shí)由Clris Torek在Berkeley DB出實(shí)作的.我找到的最確切的引文中這樣說”Chris Torek,C語言文本哈希函數(shù),UseNET消息<<27038@mimsy.umd.edu> in comp.lang.c ,1990年十月.”在Rich Salz于1992年在USENIX報(bào)上發(fā)表的討論INN的文章中提到.這篇文章可以在上找到. 33這個(gè)奇妙的數(shù)字,為什么它能夠比其他數(shù)值效果更好呢?無論重要與否,卻從來沒有人能夠充分說明其中的原因.因此在這里,我來試著解釋一下.如果某人試著測試1到256之間的每個(gè)數(shù)字(就像我前段時(shí)間寫的一個(gè)底層數(shù)據(jù)結(jié)構(gòu)庫那樣),他會發(fā)現(xiàn),沒有哪一個(gè)數(shù)字的表現(xiàn)是特別突出的.其中的128個(gè)奇數(shù)(1除外)的表現(xiàn)都差不多,都能夠達(dá)到一個(gè)能接受的哈希分布,平均分布率大概是86%. 如果比較這128個(gè)奇數(shù)中的方差值(gibbon:統(tǒng)計(jì)術(shù)語,表示隨機(jī)變量與它的數(shù)學(xué)期望之間的平均偏離程度)的話(見Bob Jenkins的<哈希常見疑問>http://burtleburtle.NET/bob/hash/hashfaq.html,中對平方差的描述),數(shù)字33并不是表現(xiàn)最好的一個(gè).(gibbon:這里按照我的理解,照常理,應(yīng)該是方差越小穩(wěn)定,但是由于這里不清楚作者方差的計(jì)算公式,以及在哈希離散表,是不是離散度越大越好,所以不得而知這里的表現(xiàn)好是指方差值大還是指方差值小),但是數(shù)字33以及其他一些同樣好的數(shù)字比如 17,31,63,127和129對于其他剩下的數(shù)字,在面對大量的哈希運(yùn)算時(shí),仍然有一個(gè)大大的優(yōu)勢,就是這些數(shù)字能夠?qū)⒊朔ㄓ梦贿\(yùn)算配合加減法來替換,這樣的運(yùn)算速度會提高.畢竟一個(gè)好的哈希算法要求既有好的分布,也要有高的計(jì)算速度,能同時(shí)達(dá)到這兩點(diǎn)的數(shù)字很少.

php技術(shù)：php-perl哈希算法實(shí)現(xiàn)(times33哈希算法)，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時(shí)間聯(lián)系我們修改或刪除，多謝。