[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Hashing, and NSDictionaries
From: |
Pascal Bourguignon |
Subject: |
Re: Hashing, and NSDictionaries |
Date: |
Tue, 12 Mar 2002 23:52:28 +0100 (CET) |
> 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------