From: Robert Klemme <bob.news@...>
Date: 2005-09-16T22:06:35+09:00
Subject: Re: Sets, uniqueness not unique.

Hugh Sasse wrote:
> On Fri, 16 Sep 2005, Robert Klemme wrote:
> 
>> Hugh Sasse wrote:
>>> On Fri, 16 Sep 2005, Robert Klemme wrote:
>>> 
>>> lo>> [1,2, 1,2].inject(0) { |a,b| ((a << 3) ^ b.hash) & 0xFFFF_FFFF}
>>>> => 1885
>>> 
>>> Ah, so that's what MAX_HASH is, I couldn't remember how big Fixnums
>>> were.
>> 
>> No, that's not really the limit - I just choose 32 bit as it's an
>> often used size. :-)
>> 
>> 13:41:59 [~]: ruby -e 'i=1;i<<=1 while Fixnum === i;i>>=1;puts
>> i.to_s(16), i.class'
>> 20000000
>> Fixnum
>> 
>>> I was thinking about something like a linear congruential
>>> random number generator like:
>>> brains hgs 22 %> irb
>>> irb(main):001:0> [2,1,1,2].inject(0) {|a,b| ((a * 31)+b.hash) %
>>> 4093082899} => 151936
>>> irb(main):002:0> [2,2,1,1].inject(0) {|a,b| ((a * 31)+b.hash) %
>>> 4093082899} => 153856
>>> irb(main):003:0> [2,1,2,1].inject(0) {|a,b| ((a * 31)+b.hash) %
>>> 4093082899} => 151996
>>> irb(main):004:0>
>>> 
>>> like
>>> http://www.cs.bell-labs.com/cm/cs/pearls/markovhash.c
>>> 
>>> from "Programming Pearls".
>> 
>> That code does only one modulus on the NHASH.  Your code does it for
>> each 
> 
> I wasn't following closely enough. :-)

Someone talked about his brain behaving like cottage cheese today... :-))

>> iteration.  But otherwise 31 seems a good number - Java containers
>> use 31, too. :-)
>> 
>>> From AbstractList:
>> 
>          [...]
>> 
>>> ------------------------------------------------ Class: Fixnum <
>>>       Integer A +Fixnum+ holds +Integer+ values that can be
>>>       represented in a native machine word (minus 1 bit). If any
>>> operation on a +Fixnum+
>>> 
>>> Should that be 0x7FFF_FFFF?  (2147483647)
>>> According to
>>> http://www.rsok.com/~jrm/printprimes.html
>>> this would seem to be a prime number, so could be used as the
>>> modulus anyway.
>> 
>> You can even use bit and on this which I would expect to be slightly
>> more efficient.
> 
> Agreed.  Is the RCR yours?

Yes.

>  Maybe an RCRCR :-) is appropriate, "change
> the hashing algorithm in that code to use LCG".

Done.

Thanks for the inspiring discussion!

    robert