From: Travis Whitton <whitton@...>
Date: 2002-10-04T03:06:15+09:00
Subject: Ruby's hashing algorhithm

There is a very interesting article over on perl.com about how hashes work.

http://www.perl.com/pub/a/2002/10/01/hashes.html

I was quite surprised to find out that in Perl 5.005 the function to convert
a hash key to an integer is as simple as:

# Return the hashed value of a string: $hash = perlhash("key")
# (Defined by the PERL_HASH macro in hv.h)
sub perlhash
{
    $hash = 0;
    foreach (split //, shift) {
        $hash = $hash*33 + ord($_);
    }
    return $hash;
}

This lead me to start wondering where Ruby "borrows" it's hash implementation
from, or if it has it's own original approach. The article states that the
current version of Perl uses a hashing algorithm developed by Bob Jenkins,
which is available via his website here.

http://burtleburtle.net/bob/hash/doobs.html

According to Jenkins' site, his algorithm is "faster and more thorough
than the one you are using now", and he goes on to describe all of the well
known hashing implementations and produce reasons why his new method is
superiour. This leads me to wonder if his implementation would be worth
investigating for future versions of Ruby(assuming Ruby isn't using this
algorithm now).

-
Travis Whitton <whitton@atlantic.net>

-- 
Bill Gates is a mean and selfish man and Microsoft reflects his inner poverty.