From: Bill Kelly <billk@...>
Date: 2008-08-18T05:50:36+09:00
Subject: Re: Not So Random (#173)


From: "Martin Bryce" <nx-2000@fastwebnet.it>
>
>  the 
> string.hash method returns SEQUENTIAL numbers for alphabetically 
> sequential strings!
> 
> I was taught that a hash function should strive to distribute the inputs 
> in its keyspace with maximal randomness, and that it should mask any 
> normally possible input pattern (those that are not a knowledgeable 
> attack at the function, I mean)..... That's not a hash function, that's 
> a checksum!
> 
> Does Ruby use such a dreadful function for its internal hash tables? If 
> so, filling a hash with previously ordered data is going to (over)fill 
> the hash buckets one by one... @___@

I'm not sure why that would follow.  The number of buckets is typically
a prime number, and the hash value is mapped to a bucket number by
modulo arithmetic.  So . . . .

>> num_buckets = 7
=> 7
>> "a".upto("z") {|x| puts "#{x} hash=#{x.hash} -> bucket=#{x.hash % num_buckets}" }
a hash=100 -> bucket=2
b hash=101 -> bucket=3
c hash=102 -> bucket=4
d hash=103 -> bucket=5
e hash=104 -> bucket=6
f hash=105 -> bucket=0
g hash=106 -> bucket=1
h hash=107 -> bucket=2
i hash=108 -> bucket=3
j hash=109 -> bucket=4
k hash=110 -> bucket=5
l hash=111 -> bucket=6
m hash=112 -> bucket=0
n hash=113 -> bucket=1
o hash=114 -> bucket=2
p hash=115 -> bucket=3
q hash=116 -> bucket=4
r hash=117 -> bucket=5
s hash=118 -> bucket=6
t hash=119 -> bucket=0
u hash=120 -> bucket=1
v hash=121 -> bucket=2
w hash=122 -> bucket=3
x hash=123 -> bucket=4
y hash=124 -> bucket=5
z hash=125 -> bucket=6


I'm far from an expert on such matters... but it's not clear to me why
sequential hash values would be a problem for this application?


Regards,

Bill