Re: Hashing, and NSDictionaries

[Pascal Bourguignon]

> From: Stephen Brandon <stephen@brandonitconsulting.co.uk>
> Date: Tue, 12 Mar 2002 19:14:04 +0000
> 
> Hi,
> 
> Just a query about the way NSDictionaries do their lookups.
> 
> It seems that although NSDictionary creates a hash of all keys handed to it, 
> once it finds a match between a stored hash and the hash of a (possible) key 
> sent to it, it then does an isEqual: between the stored key and the query key.
> 
> Why is this final equality check necessary? Isn't the fact that it already 
> has a hash of the stored key and the query key, and the fact that they match, 
> good enough?
> 
> In my situation, my -isEqual does a new hash of self and the other object and 
> compares them -- so the number of hashes done can be very large! And there's 
> quite a lot of redundant hashing going on.
> 
> Can anyone shed any light on this?
> 
> Cheers,
> Stephen Brandon

Obviously, some  objects may need  more than the  32 bits of  the hash
value to store  their state. So, in the set of  these objects, you can
have two different objects with the same hash value.

If you  cannot have  more than 2^32  different objects in  your class,
then you're right  to compare them just comparing  a 32-bit hash value
of them.  But  then, why compute the hash value,  why not just compare
their 32-bit  value ?  My point here  is that  the reason we  use hash
values in the  first place is because we're  dealing with objects that
have more  than 32-bit of state,  that is, classes where  there can be
much more than 2^32 different objects.


Moreover, note that even in the case of a class such as:

     @interface SimpleStuff:NSObject
     {
        unsigned int  kind_of_stuff;
     }
        -(unsigned)hash;
        // { return kind_of_stuff; }

        -(BOOL)isEqual:anObject;
        // { return [anObject kindOfStuff]==kind_of_stuff; }
        
     @end // SimpleStuff

you cannot make  the assumptions you're making. First  notice that you
have to  write [anObject kindOfStuff]  to compare it to  a SimpleStuff
instance, because  you cannot  know if anObject  is of the  exact same
class. Mainly because, second, anObject or all you SimpleStuff objects
could be of a subclass of SimpleStuff that would add for example 1Mbit
of  state.   If these  subclasses  relied  on  your implementation  of
isEqual:,  they would  have  a lot  of  distinct instances  considered
equal.


-- 
__Pascal_Bourguignon__              (o_ Software patents are endangering
()  ASCII ribbon against html email //\ the computer industry all around
/\  and Microsoft attachments.      V_/ the world http://lpf.ai.mit.edu/
1962:DO20I=1.100  2001:my($f)=`fortune`;  http://petition.eurolinux.org/

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/IT d? s++:++(+++)>++ a C+++  UB+++L++++$S+X++++>$ P- L+++ E++ W++
N++ o-- K- w------ O- M++$ V PS+E++ Y++ PGP++ t+ 5? X+ R !tv b++(+)
DI+++ D++ G++ e+++ h+(++) r? y---? UF++++
------END GEEK CODE BLOCK------