From: "Marcin Mielżyński" <lopx@...>
Date: 2007-09-10T08:50:10+09:00
Subject: Re: Hash

Ron Green pisze:
> Phlip wrote:
>> Ron Green wrote:
>>
>>> When I said it couldn't be used for identity I meant if you can't
>>> guarantee uniqueness.How would you know if you retrieved the correct
>>> data.
>> You don't need uniqueness. The hash did its job when you can almost
>> instantly chop billions of strings down to a short list of candidate
>> strings. After the hash collision, you trivially search the list for the
>> actual target. The point is to access the stored value, at the target
>> location, quickly!
>>
>> This is how Google works, for example...
> 
> Thank you.

Here is an example:

a class whose instances have always the same #hash and #eql? which 
always returns true

class Foo
     def hash
         puts "hash called"
         0
     end

     def eql? other
         puts "eql? called"
         true
     end
end


h = {}
f1 = Foo.new
f2 = Foo.new

# given

h[f1] = :blah

here, f1.hash is used to locate the bucket to be inserted into, so it 
will only output "hash called".

h[f1]

here, the f1.hash is used to locate the bucket and then references will 
be compared (f1 is identical to f1 so eql? won't have to be called).

h[f2]

here, the f2.hash is used to locate the bucket, it will be found, but f2 
is not identical to f1, so eql? method will have to be used (which in 
turn returns true, so the objects are considered equal) and finally the 
lookup will be successfull.


In a hash, when two different objects return the same hash value, it's 
called a collision. Equality operation here just atcs like a guard to 
make sure we are dealing with right object.

lopex