Shulou(Shulou.com)06/03 Report--

This article will explain in detail how to implement the hashing algorithm in php-perl. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

The code is as follows:

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

* 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; pendant +) {

Hash = hash * 33 + * p

}

* klen = p-key

}

Else {

For (p = key, I = * klen; I; iMurray, pendant +) {

Hash = hash * 33 + * p

}

}

Return hash

}

This is the famous times33 hash algorithm, which is adopted by perl language and appears in Berkeley DB. It is one of the best known hash algorithms. It has very fast computing efficiency and good hash distribution when dealing with hashes with strings as keys. Dan Bernstein was the first to propose this algorithm, but the source code is indeed implemented by Clris Torek in Berkeley DB. The most exact quotation I can find says, "Chris Torek,C text hash function, Usenet message."

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.