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. :-)

> 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?  Maybe an RCRCR :-) is appropriate, "change
the hashing algorithm in that code to use LCG".
>
> Kind regards
>
>    robert

         Hugh