From: Rick DeNatale <rick.denatale@...>
Date: 2009-09-11T01:49:34+09:00
Subject: Re: What’s the best general implementation of custom #hash methods?

On Thu, Sep 10, 2009 at 11:56 AM, Shot (Piotr Szotkowski)<shot@hot.pl> wrote:
> Hello, ruby-talk.
>
> What’s the best (fast, yet with relatively few cases when equal hashes
> are generated for non-eql objects) way to implement a hash method?
>
> Is XOR-ing the hashes of an object’s instance variables (assuming that
> two objects are eql if their ivars are eql) a good general approach?
>
> I’m asking because I use this pattern in my code, and it seems quite
> fast; I needed to work around a bug in MRI’s Set#hash and this solution¹
> seems about as fast as the original MRI’s Set#hash. I’m just not sure
> whether it’s hashy enough (so to speak) in that two un-eql objects
> hashed in this way produce different hashes often enough.
>

Well, let's look at how Array#hash works here's the 1.8 C code:

static VALUE
rb_ary_hash(ary)
    VALUE ary;
{
    long i, h;
    VALUE n;

    h = RARRAY(ary)->len;
    for (i=0; i<RARRAY(ary)->len; i++) {
	h = (h << 1) | (h<0 ? 1 : 0);
	n = rb_hash(RARRAY(ary)->ptr[i]);
	h ^= NUM2LONG(n);
    }
    return LONG2FIX(h);
}

This looks like a typical cryptographic hash algorithm pattern
combining bit rotation and xor.  It seeds the value with the length of
the array, then for each element, rotates the value 1 bit to the left,
then xors in the elements hash.

This scrambles the bits more than just a straight xor


-- 
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale