From: Michael Bevilacqua-Linn <michael.bevilacqualinn@...>
Date: 2007-09-10T05:18:33+09:00
Subject: Re: Hash

------=_Part_4853_12311374.1189369103766
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

No hash function is guaranteed to be unique for all inputs.  I don't know
what exactly you mean by "can't be used for identity".

The hash method on string (and any other object) is used by ruby when
storing that type of object in a hash table.  Haven't looked through the
ruby sources, but here's how this sort of thing generally works and the
problem that we're trying to solve.

We want a data structure that lets us retrieve some key/value pair in
(hopefully) constant time.  This means that, no matter how many items of
data we're storing, it will always take us (roughly) the same amount of time
to retrieve an arbitrary item.  (IE: O(1))  A simple way to do this is to
have some hash function that breaks our inputs up into "buckets".  Then,
when we get a given input, we feed it into that function and look into the
"bucket" that it gives us back.

An example of a very simple hash function for ASCII strings would be
something like this:

Sum the ASCII values of each character in the string, then take he modulus
of that value and 10.  This would give us ten "buckets" to look in.
Obviously, there will be a whole lot of overlap here, as we have arbitrary
length strings as inputs to our hash function and only 10 possible outputs
(so this is not a reversible function.)

We get around this problem by storing the values in each bucket in some
other data structure, say a linked list.  We then get the bucket (using the
hash function) and search through the list for our value.

A simple example using the hash function I described above (which is *not*
ruby's builtin string hash function.)...  Both "a" and "k" would fall into
the same bucket:

irb(main):021:0> "a"[0] % 10
=> 7
irb(main):022:0> "k"[0] % 10
=> 7

So if we wanted to store the keys "a" and "k" in our hash table, they would
both live in bucket seven.  Within bucket seven, they would have some
internal organization that lets us retrieve them once we know the bucket
(say a linked list).  So if we want to find the value associated with the
key "a" we would perform our hash function on "a" and get bucket 7.  We
would then look through the list located in bucket 7 until we find the value
a, and retrieve the value associated with that key.

Ruby's hash tables would work in a similar way, though I don't know what
sort of data structure they use internally to the buckets.  (It could be
anything, of course, not just a linked list.)

So you probably would not use string.hash directly often (if ever), but
every time you do something like aHash = {"foo" => 42), it's being used by
ruby.

Again, any decent data structures book will explain this better than I can,
if you're truly interested.   :-)

MBL

>
> Peter,
> If Its not guaranteed to be unique, then it can't be used for identity.
> Can you give me an example of how i would use string.hash?
> --
> Posted via http://www.ruby-forum.com/.
>
>

------=_Part_4853_12311374.1189369103766--