From: "Mauricio Fernández" <batsman.geo@...>
Date: 2002-08-15T04:28:01+09:00
Subject: Re: Primary Key Hash help

On Wed, Aug 14, 2002 at 11:11:52PM +0900, Michael Campbell wrote:
> > 
> > N> Just wondering: I saw the MD5 solution, but feel that I am missing
> > N> something. Why MD5 instead of:
> > N> 	key = row.hash
> > 
> > pigeon% ruby -e 'p "Robertsons".hash == "Sutton".hash'
> > true
> > pigeon% 
> 
> I think we addressed the non-uniqueness of any hash algorithm
> initially and the original author was aware of it.

But it seems collisions are frequent with String#hash.
It's a fast function but it "fills" the image domain less uniformly than
MD5. Plus its width is that of a Fixnum (31 bits...), compared to MD5's
128. MD5's result space is 29 orders bigger than String#hash's. 
It's no surprise collisions are _far_ more probable :-)

> Are you simply saying here that Ruby's hash algorithm is... bad?

[pertinent source code below]
It seems Ruby could also use Perl's hash algorithm.

Google gives this reference to Perl's algorithm:
http://mail-index.netbsd.org/tech-perform/2001/11/28/0006.html
which discusses its performance vs other functions.

The first algorithm is PJ Weinberg's hash function.
Ruby uses the last one, unless told otherwise (you'd have to change
config.h). I don't know how well it compares to the others in terms of
speed and "one-way-ness", but these algorithms should be pretty much
similar performance-wise.

    register long len = RSTRING(str)->len;
    register char *p = RSTRING(str)->ptr;
    register int key = 0;

#ifdef HASH_ELFHASH
    register unsigned int g;

    while (len--) {
        key = (key << 4) + *p++;
        if (g = key & 0xF0000000)
            key ^= g >> 24;
        key &= ~g;
    }
#elif HASH_PERL
    while (len--) {
        key = key*33 + *p++;
    }
    key = key + (key>>5);
#else
    while (len--) {
        key = key*65599 + *p;
        p++;
    }
    key = key + (key>>5);
#endif
    return key;
}

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com
  
The most important design issue... is the fact that Linux is supposed to 
be fun...
	-- Linus Torvalds at the First Dutch International Symposium on Linux