Re: Implementing isEqual: and hash
Re: Implementing isEqual: and hash
- Subject: Re: Implementing isEqual: and hash
- From: Peter Duniho <email@hidden>
- Date: Sat, 23 Aug 2008 17:20:44 -0700
Date: Sat, 23 Aug 2008 12:05:44 -0700
From: "Adam R. Maxwell" <email@hidden>
[...]
- (BOOL)isEqual:(id)other
{
if ([other isKindOfClass:[self class]] == NO) return NO;
return ([ivar1 isEqual:(Test *)other->ivar1] && [ivar2 isEqual:
(Test *)other->ivar2]);
}
- (unsigned)hash { return [ivar1 hash]; }
@end
I believe it's sufficient to use [ivar1 hash], since the object is
only equal if ivar1 is equal in both objects. I was just curious to
know what you gain by using ([ivar1 hash] ^ [ivar2 hash]); is it
possible to know in general if it reduces collisions?
If you combine the hash values correctly, it will reduce collisions.
Note that the previously mentioned "xor" technique is not generally
considered "correct" and can in fact lead to increased collisions,
not fewer.
One reasonably common technique for combining hash values into a new
hash value is to "multiply and accumulate" using a prime number.
There's probably some good math theory as to what a nice prime number
to pick might be, but I've seen enough examples that use 37 that
that's what I usually use. :)
For example:
- (unsigned) hash
{
unsigned ret = 0;
ret += ret * 37 + [ivar1 hash];
ret += ret * 37 + [ivar2 hash];
return ret;
}
Note the redundant multiply and add in the first line. Writing the
code that way makes it easy to add/remove members if for some reason
the data structure should change in the future. But it would be just
as correct to simply initialize ret to the first hash value, of course.
Presumably that
depends on the hash table implementation as well.
Well, if your hash values collide, they collide regardless of the
hash table. As long as you've got a well-distributed hash function,
any collisions generated by the hash table implementation should be
well-distributed as well.
Pete
_______________________________________________
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