Re: When do I need to override hash?
Re: When do I need to override hash?
- Subject: Re: When do I need to override hash?
- From: Richard Frith-Macdonald <email@hidden>
- Date: Fri, 21 Aug 2009 10:52:07 +0100
On 21 Aug 2009, at 10:31, Alastair Houghton wrote:
On 21 Aug 2009, at 10:07, Jean-Daniel Dupas wrote:
Excuse my intrusion in this discussion, but I don't really
understand why 'isEqual:' and 'compare:' results must not change
when an object is used as key.
My though was that as long as the hash remain the same, it should
not be an issue. I don't see any case where it may be useful, but
don't see why it would be illegal ?
In the current implementation, I think you're probably right that -
isEqual: and -compare: could change their results as long as -hash
stayed the same.
I very much doubt that.
The normal implementation for a hash based storage system is to have a
number of 'buckets' N, and assign a key object to a particular bucket
using (hash % N).
Each bucket might be implemented as an array or as a linked list or
some other data structure, but whatever it is, if it contains more
than one key object, the implementation picks the correct one by
searching the bucket using -isEqual: or -compare:
So, if you change the result of -isEqual: and -compare: for a key in a
bucket, there is no longer any way to find that key (the hash only
narrows down the search to the correct bucket) and the collection is
broken.
That's why it's illegal to change the results of either -compare: and -
isEqual: for a key in a dictionary or a member of a set.
_______________________________________________
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