Hash

ruby-talk
21

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

22

Excellent! Thanks! I don't know if I've ever seen it explained so
clearly. That makes a lot more sense to me now. (And naturally,
disregard where I said Object#equal in my other post. Couldn't
remember positively if it was "equal" or "eql?". :wink: )

Anyways, good stuff. I actually need to do this myself soon enough...

···

On Sep 9, 6:49 pm, Marcin Miel y ski <l...@gazeta.pl> wrote:

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