Re: [dev] The mysterious 31

It's about entropy and maths. Not magic. This way you rotate over the
most changing bits (lower) of each char of the string while reapplying
the current calculation over the previous result. In r2 I use
something similar in util/str.c

In Java they use similar algorithm.

I think the book 'icant remembre the name' about hacker-algorithms'
may explain it better

On Aug 4, 2010, at 5:03 AM, Kris Maglione <maglione.k_AT_gmail.com> wrote:

> On Tue, Aug 03, 2010 at 09:53:27PM -0400, Jacob Todd wrote:
>> In K&R, chapter 6, section 6, there is a funtion called hash that
>> hashes a
>> string, which will be stored in a linked list. The function in
>> question is on
>> page 144, but here it is for those of you who don't have K&R handy.
>>
>> /* hash: form hash value for string s */
>> unsigned
>> hash(char *s)
>> {
>> unsigned hashval;
>>
>> for(hashval = 0; *s != '\0'; s++)
>> hashval = *s + 31 * hashval;
>> return hashval % HASHSIZE;
>> }
>>
>> So what is the purpose of the magic 31? The only thing that I think
>> might be a
>> reference to what it may be for is the paragraph prior, which states
>>
>> The hashing function, ..., adds each character value in the
>> string to a
>> scrambled combination of the previous ones and returns the
>> remainder
>> modulo the array size.
>>
>> Does the magic 31 have to do with scrambling?
>
> It's just an arbitrary number that happens to perform well in that
> particular hash function. There isn't much science to hash
> functions, but some of them prove to have good performance and good
> distribution, others, not so. I tend to use Dan Bernstein's hash
> function, which uses 33. It's not magic, it's just been shown to
> work well. Although, in this case, I suspect that it was chosen
> because it optimizes to a particularly fast addition/binary shift,
> but so do a lot of other choices.
>
> static ulong
> hash(const char *str) {
> ulong h;
>
> h = 5381;
> while (*str != '\0') {
> h += h << 5; /* h *= 33 */
> h ^= *str++;
> }
> return h;
> }
>
> --
> Kris Maglione
>
> You talk when you cease to be at peace with your thoughts.
> --Khalil Gibran
>
>
Received on Wed Aug 04 2010 - 10:05:31 CEST