Re: How to use custom comparison for matching in Dictionary?

[Thomas Tempelmann <tempelmann@gmail.com>]

On Mon, Mar 29, 2010 at 23:26, Andrew Keller <andrew@kellerfarm.com> wrote:
> If two separate objects generate the same hash value, then the Dictionary 
>considers them them to be identical.

I sure hope not!

A dictionary, using key-value coding, may use a hash only for
optimization but not for the final decision on what keys are equal.
That would be very bad, as the very nature of hash values allows two
objects or values to have the same hash value, even if they are not
equal.

Instead, there's a "collision" concept and a list involved: Different
values with same hash values are all remembered in a list, and when
looking up a value, the list behind its hash value must be search. So,
in a way, a dictionary using a hash table is only reducing the number
of searches it would have to do, and its cost is more memory usage.

Funny though - Aaron Ballman had the same misconception a few years
ago, and that led to an obscure, thus nasty, bug in the code managing
WeakRefs, leading to the occasional leak or crash.

And yes, there are hash table algorithms that ensure that there are no
collisions. But they require certain requisites, and thus are a
special form. The common rule for dictionaries using hash tables,
though, is that collisions happen and that's not enough to do the
matching.

HTCIUFY,
  Thomas

-- 
Thomas Tempelmann, http://www.tempel.org/

_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>

Search the archives:
<http://support.realsoftware.com/listarchives/lists.html>