On 21 Aug 2009, at 10:52, Richard Frith-Macdonald wrote:
On 21 Aug 2009, at 10:31, Alastair Houghton wrote:
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.
Because? The key here is the words "in the current implementation"...
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).
...so why are you talking about "the normal implementation"? How
about we discuss this in terms of the *actual* implementation, since
we have it? This thread contains far too much theorising about how
all of this works and not enough looking at how it *actually* works.
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:
FWIW, the actual implementation isn't based on the technique you're
talking about here (which is generally called separate chaining), but
it uses linear probing (see e.g. Sedgewick if you're interested in the
details). It still, of course, needs to be able to test keys for
equality with -isEqual:.
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.
Well, no.
Since we're talking about actually mutating the key (effectively
inside the data structure, though of course it's really storing just a
reference), as long as [key isEqualTo:key] is YES (and if not, your
key is not sane anyway), you'll be able to find it just fine.
The only problem I can think of that you might create is if you have
two keys key1 and key2, and when data was originally added, [key1
isEqualTo:key2] was NO, but because of a mutation of one or other,
[key1 isEqualTo:key2] changes to YES. In that case, you'll get odd
behaviour.
FWIW, if there were trees involved (which right now there can't be,
because there is no requirement to implement -compare: for collection
keys in general), it is additionally true that [key1 compare:key2]
would have to be an invariant for any pair of keys key1 and key2.
Even then, that doesn't mean you can't change things that -compare:
depends upon... you'd just have to be careful not to violate the
ordering constraint.
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.
Whether or not it's illegal per se, it's *certainly* a bad idea and
shouldn't be encouraged or relied upon.
Kind regards,
Alastair.
--
http://alastairs-place.net
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
