Re: NSDictionary key types
Re: NSDictionary key types
- Subject: Re: NSDictionary key types
- From: "Stephen J. Butler" <email@hidden>
- Date: Thu, 6 Jan 2011 15:57:47 -0600
On Thu, Jan 6, 2011 at 3:17 PM, Jon Sigman <email@hidden> wrote:
> Do the following two objects have the same hash value, and if so, why do thay?
> How is it assigned?
> id myStr1 = @"8760";
> id myStr2 = @"8760";
Long Rambling:
Note: if [myStr1 isEqual:myStr2] then [myStr1 hash] == [myStr2 hash].
That's part of the contract mandated by the NSObject protocol. If you
write your own isEqual: method then you must make sure that hash
behaves properly.
HOWEVER, the converse is not always true. For example, if [myStr1
hash] == [myStr2 hash] then you can't say anything about [myStr1
isEqual:myStr2]. That could return YES, it could return NO.
The object to hash value relationship is many-to-one: many different
objects hash to the same value. This is trivially easy to see since
you can construct an infinite number of strings, but there are only
2^32 or 2^64 hash values possible. But hashes aren't meant to uniquely
identify objects, they're just meant as a convenient way to divide
them into partitions/buckets.
Now, the gotcha: the default NSObject implementation of isEqual: just
compares pointers (IIRC). In your contrived example, the compiler does
some magic to collect all constant strings together and eliminate
duplicates, so myStr1 and myStr2 will point to the same object. But it
doesn't matter, because NSString overrides isEqual: to do a proper
string comparison. It also overloads hash to return a good value
(Google "hash strings" to see many, many hashing algorithms).
Suppose you had this class:
@interface Foo : NSObject {
NSString *bar;
}
- (id) initWithString:(NSString*)aString;
@end
@implementation Foo
- (id) initWithString:(NSString*)aString {
if (self = [super init])
bar = [aString copy];
}
- (void) dealloc {
[bar release];
[super dealloc];
}
@end
Now, what happens here?
Foo *f1 = [[[Foo alloc] initWithString:@"foo"] autorelease];
Foo *f2 = [[[Foo alloc] initWithString:@"foo"] autorelease];
What is the result of [f1 isEqual:f2]? Taking what I said before about
the default implementation of isEqual:, it returns NO! You probably
don't want that. So let's add an isEqual:
- (BOOL) isEqual:(id)other {
if (![other isKindOfClass:[Foo class]])
return NO;
else
return [bar isEqual:((Foo*)other)->bar];
}
Good, now [f1 isEqual:f2] returns YES. However, [f1 hash] != [f2 hash]
because, again, the NSObject base implementation of hash doesn't do
anything special. So we need to solve that for our custom object too:
- (NSUInteger) hash {
return [bar hash];
}
See what I did? I just passed off the responsibility of my isEqual:
and hash methods to the instance variable(s) in my class that
ultimately determine equality and the hash value. If I had two
instance variables, I might do [bar isEqual:((Foo*)other)->bar] &&
[baz isEqual:((Foo*)other)->baz] along with [bar hash] ^ [baz hash].
But hopefully you get the idea.
Now, if you're going to do this on a larger scale, there are a bunch
of caveats in the NSObject protocol documentation you should pay
attention to. Notably, isEqual: must be commutative [f1 isEqual:f2] =>
[f2 isEqual:f1] and that the hash value must not change under
mutation.
But that's all really advanced stuff and only something I've had to
think about 2 times in all the years I've done Cocoa. Most developers
never bother with it. Just trust that it works and be happy.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden