[ruby-talk:9645] Re: Strange Hash behavior

On Sun, 21 Jan 2001, ts wrote:

> >>>>> "B" == Ben Tilly <[e-mail]> writes:
> 
>  ruby version
> 
> B>   def hash (string)
> B>     hash_val = 0
> B>     for byte in string.each_byte do
> B>       hash_val = 33*hash_val + byte
>                     ^^
>                     997
> B>     end
> B>     hash_val += hash_val/32
> B>   end
> 
>  ruby can use the hash function given in the Dragon Book (compiled with
>  -DHASH_ELFHASH), perl hash function (compiled with -DHASH_PERL) or it's
>  own hash function.
> 
>  On /usr/share/dict/words the ruby hash function give less collisions
>  than the perl hash function. Compile ruby with -DHASH_LOG to know the
>  number of collisions.

Thanks Ben and Guy, for the extra information.

I thought it might be beneficial for someone to know the hash
functions for all classes (I could easily find), so here they are:

Array:
    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 INT2FIX(h);

Bignum:
    key = 0; digits = BDIGITS(x); len = RBIGNUM(x)->len;
    for (i=0; i<len; i++) {
	key ^= *digits++;
    }
    return INT2FIX(key);

Float:
    d = RFLOAT(num)->value;
    c = (char*)&d;
    for (hash=0, i=0; i<sizeof(double);i++) {
	hash += c[i] * 971;
    }
    if (hash < 0) hash = -hash;
    return INT2FIX(hash);

Time:
    GetTimeval(time, tobj);
    hash = tobj->tv.tv_sec ^ tobj->tv.tv_usec;
    return INT2FIX(hash);

String:
    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
    if (ruby_ignorecase) {
	while (len--) {
	    key = key*33 + toupper(*p);
	    p++;
	}
    }
    else {
	while (len--) {
	    key = key*33 + *p++;
	}
    }
    key = key + (key>>5);
#else
    if (ruby_ignorecase) {
	while (len--) {
	    key = key*65599 + toupper(*p);
	    p++;
	}
    }
    else {
	while (len--) {
	    key = key*65599 + *p;
	    p++;
	}
    }
    key = key + (key>>5);
#endif
    return key;




     - Aleksi