Re: When do I need to override hash?
On Aug 20, 2009, at 9:09 PM, Jeff Laing wrote: If you need to know whether or not another object has put your object into an NSDictionary, you're probably doing something wrong. Do you have a specific concern about Core Data using your objects ? No, I guess the point I was trying to make was that this discussion seemed to have touched on if you put your objects into an NSSet then you'll need to be more careful about the implementation of - hash, etc. I was trying to point out that just because my application code doesn't go anywhere near NSSet, its conceivable (to me) that Core Data (for example) might be storing dirty objects in an NSSet behind your back. So you can't not implement -hash, etc properly and hope everything will work. There may be any number of external technologies (Core Data was just an example) that may be using your objects in ways you aren't expecting, and there's no future-proof way you can cut corners. There really isn't any point in cutting corners here. If you need to do something unusual, you can use a CFDictionary with custom callbacks. - Ben ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 22:19, Adam R. Maxwell wrote: On Aug 20, 2009, at 9:44 PM, Quincey Morris wrote: The keys in a dictionary (or other keyed collection, like a map table) need to be immutable objects, but that's unrelated to the hash. Mutability in the keys would be bad, hash or no hash. What do you mean by immutable? You can put a mutable object in a hashing collection as long as its -hash and -isEqual: do not depend on mutable state. For instance, if you configure a CFDictionary to use pointer equality and hash for its keys, you can use an NSMutableString as a key. First, I'm sorry, this time it was me who misspoke. Mutability of the key isn't the problem -- mutating the key is the problem. Second, part of what I meant was kind of mundane -- if you mutate an object used as a key, you're likely to have trouble *finding* it again because ... the key changed. Obviously there are scenarios where you'd know what the mutated key was (e.g. you stored a pointer to the key somewhere, or it changed in a very controlled way), so it might be fine, but it sure sounds confusing. Third, if you configure a CFDictionary to use pointer equality and hash for its keys, you're not really using a NSMutableString as a key, you're effectively using the object pointer as a key (which is itself an immutable entity) -- you've effectively abandoned the stringiness in regard to the keys. Separately, collections use isEqual: on the object values to determine equality, when they care. (I doubt that NSDictionary cares about object value equality, but NSSet certainly does, as does NSArray, when asked to compare objects.) Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) I use NSMutableStrings as values (not keys) in NSDictionary and expect that to work, even though hash/isEqual: of those strings is certainly changing while in the collection. CFDictionary at least doesn't include a hash function in its value callback, although it does require an equality function. From my quick look at the source, the only place that equality callback is used is in testing CFEqual(dict1, dict2), CFDictionaryGetCountOfValue(), and CFDictionaryContainsValue(). I already got beaten up about this, and my answer is that it's not 100% clear that it's always safe. It's not outside the bounds of possibility that a very large dictionary may use a different memory strategy that involves object hash values, though I agree it seems rather unlikely (and you've found further evidence against the idea). Seems like it ought to be documented, otherwise you're always going to be betting on your guess about the implementation. ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 23:24, Adam R. Maxwell wrote: It was not my intent to beat up on you, so I apologize if I came across that way! Nah, I was just kidding -- and trying to distract your attention away from the fact that I didn't have a better answer. ___ 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
Re: When do I need to override hash?
On 21 Aug 2009, at 03:45, Jeff Laing wrote: The -hash method is important for objects that are used as keys in associative collections. [snip] So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts) ... Is there any way that you can tell that some higher-level technology you are using (CoreData?) is putting your objects into an NSSet? That's presumably a hidden implementation detail which you can't assume one way or the other with any safety? If it did that without documenting that mutating them would be A Bad Thing, then that would be a bug in the higher-level technology in question IMO. In any case, if a higher layer was storing references to your objects, it's more likely to want the thing it stores them in to work based on the pointers (i.e. the object's identity), rather than the object's value. So it's quite unlikely that this would be a problem in practice either. 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
Re: When do I need to override hash?
On 21 Aug 2009, at 04:51, Seth Willits wrote: On Aug 20, 2009, at 2:31 PM, Alastair Houghton wrote: The -hash method is important for objects that are used as keys in associative collections. The documentation, nor did many others' comments on this topic, make it clear that the mutability is only a problem for the *keys*. Others and the docs talk about (paraphrasing) putting an object into a collection, not using an object as a key in an associative collection. Here are the docs: If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. Indeed. This sentence could do with being made clearer IMO; my guess is that it was written that way because people don't really think of NSSet (or NSSet-like collections) as having keys per se, but it does of course apply to objects held in an NSSet. If it were only an issue for keys, then this is, like you said, no big deal. If my reading of the documentation is correct, then it's a much more prevalent problem, as others seem to be saying. It *is* an issue for the keys (which includes objects that are held by an NSSet or NSSet-like collection). That's why I said this particular discussion was getting a bit crazy. It is perfectly safe to mutate objects stored in an NSDictionary as long as their keys don't change. The thing you mustn't change is the key's value, as determined by -isEqualTo: and -hash: (and, if implemented, -compare:). 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
Re: When do I need to override hash?
On 21 Aug 2009, at 05:44, Quincey Morris wrote: On Aug 20, 2009, at 20:51, Seth Willits wrote: The documentation, nor did many others' comments on this topic, make it clear that the mutability is only a problem for the *keys*. Others and the docs talk about (paraphrasing) putting an object into a collection, not using an object as a key in an associative collection. Yes. I believe Alastair misspoke. Not at all. hat he said is actually 99.9% true, but establishes a different point. The keys in a dictionary (or other keyed collection, like a map table) need to be immutable objects, but that's unrelated to the hash. Mutability in the keys would be bad, hash or no hash. (Newbies please ignore the next bit.) Well... somewhat perversely, what matters in Cocoa is the notional value of the key (as determined by -isEqualTo:, -hash and possibly - compare:). The *actual* contents don't matter, so it's OK to use *your own* mutable objects as keys provided that the value isn't based on anything mutable. Using an NSMutableString or some other mutable object from the frameworks would be Very Bad, because mutating them will change their value, but that isn't true for all objects. Separately, collections use isEqual: on the object values to determine equality, when they care. (I doubt that NSDictionary cares about object value equality, but NSSet certainly does, as does NSArray, when asked to compare objects.) Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) It's better to think of NSSet as a collection that has only *keys*. And NSDictionary doesn't hash objects; you can look at the implementation in CoreFoundation if you want. So object values must also follow the isEqual:/hash rules. If you implement -isEqual:, you should implement -hash and make sure that two objects for which -isEqual: returns YES return the same hash value. That, however, is not what we're discussing here; we're currently discussing the risk associated with mutable objects in collections, and I stand by my previous post. So AFAIK your reading of the documentation is absolutely correct. Object values cannot be mutated while in a collection, unless their hash value doesn't depend on the mutated properties. No, not true. Key values cannot be mutated while used in a collection, period. Correct. The confusion stems from cases like NSSet where it isn't obvious, perhaps, that the objects in the NSSet are actually *keys* rather than values. 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
Re: When do I need to override hash?
On 21 Aug 2009, at 06:48, Quincey Morris wrote: On Aug 20, 2009, at 22:05, Jeff Laing wrote: If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. It is absolutely possible that NSDictionary does not use hash values to determine the object's position in the collection and so would be exempt from the above restriction. You're conflating keys and values here. NSDictionary *does* use hash values to determine the object's position in the collection for its keys. It does not do so for its values. Likewise with NSSet (which I think is best thought of as only having keys). It's also possible (maybe even likely) that NSArray doesn't use hash values to determine the object's position in the collection. Of course not :-) It uses the array index. So, now that you mention it, I guess we don't know for sure which collections do and do not depend on hash values for this purpose. We do, because we have the source code (most of it, anyway). It's in the CF project in the Darwin sources. (It's certainly conceivable that both NSDictionary and NSArray do use object hash values to manage their internal storage, perhaps only for very large collections.) Well, leaving aside the fact that we have the code, it isn't really conceivable that NSArray would work this way (since it has to maintain an ordering, and you can't really do that with a hash table); in fact, for very large collections I think NSArray will use a 2-3 tree representation internally. In any case I can't see why it would ever depend on -hash. It doesn't make much sense in NSDictionary's case either, since the operation NSDictionary is optimised for is looking up a value given a key. How exactly would the *value*'s -hash help when doing that? I can't think how it could ever be useful. 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
Re: When do I need to override hash?
Le 21 août 2009 à 10:55, Alastair Houghton a écrit : On 21 Aug 2009, at 05:44, Quincey Morris wrote: On Aug 20, 2009, at 20:51, Seth Willits wrote: The documentation, nor did many others' comments on this topic, make it clear that the mutability is only a problem for the *keys*. Others and the docs talk about (paraphrasing) putting an object into a collection, not using an object as a key in an associative collection. Yes. I believe Alastair misspoke. Not at all. hat he said is actually 99.9% true, but establishes a different point. The keys in a dictionary (or other keyed collection, like a map table) need to be immutable objects, but that's unrelated to the hash. Mutability in the keys would be bad, hash or no hash. (Newbies please ignore the next bit.) Well... somewhat perversely, what matters in Cocoa is the notional value of the key (as determined by -isEqualTo:, -hash and possibly -compare:). The *actual* contents don't matter, so it's OK to use *your own* mutable objects as keys provided that the value isn't based on anything mutable. Using an NSMutableString or some other mutable object from the frameworks would be Very Bad, because mutating them will change their value, but that isn't true for all objects. Separately, collections use isEqual: on the object values to determine equality, when they care. (I doubt that NSDictionary cares about object value equality, but NSSet certainly does, as does NSArray, when asked to compare objects.) Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) It's better to think of NSSet as a collection that has only *keys*. And NSDictionary doesn't hash objects; you can look at the implementation in CoreFoundation if you want. So object values must also follow the isEqual:/hash rules. If you implement -isEqual:, you should implement -hash and make sure that two objects for which -isEqual: returns YES return the same hash value. That, however, is not what we're discussing here; we're currently discussing the risk associated with mutable objects in collections, and I stand by my previous post. So AFAIK your reading of the documentation is absolutely correct. Object values cannot be mutated while in a collection, unless their hash value doesn't depend on the mutated properties. No, not true. Key values cannot be mutated while used in a collection, period. Correct. 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 ? ___ 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
Re: When do I need to override hash?
No, not true. Key values cannot be mutated while used in a collection, period. Correct. 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 ? Forget my question, I just see this comment from Quincey which give me an answer. [Actually, for all I know, key values *can* be mutated while used in a collection, provided the hash value doesn't change, but even if it technically feasible it sounds so un-useful I'd argue it's better just to assert that it's not allowed.] ___ 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
Re: When do I need to override hash?
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. The key words are current implementation. For instance, Apple might decide in future to change NSDictionary and/or NSSet such that there is an implementation that uses a balanced tree rather than a hash table. I'm not saying that they will, and obviously if they did they'd need to make -compare: compulsory for the keys in such a thing (which in practice probably means they'd want to use a new subclass of NSDictionary/NSSet, and in Core Foundation add new creation APIs), and the structure would depend on the comparison results rather than the hash values. Also, I think it's a mistake to confine oneself to thinking solely about the provided collection classes. There are certainly uses for ordered associative collections, and the most likely implementations would rely critically on the behaviour of -compare:. So on that particular point, I agree with Quincy :-) 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
Re: When do I need to override hash?
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 (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
Re: When do I need to override hash?
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
Re: When do I need to override hash?
AFAIK, NSDictionary specifies that it COPIES keys, and RETAINS objects. Thus even if you were to use an NSMutableString as a key, you could not mutate the key in the NSDictionary. So the only way you are likely to get into trouble with keys is if you do troublesome things like use oddball mutable-only object types (or immutable collections with mutable content objects, or objects with mutable properties) as dictionary _keys_. So don't do that. ___ 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
Re: When do I need to override hash?
On Fri, 2009/08/21, Quincey Morris quinceymor...@earthlink.net wrote: From: Quincey Morris quinceymor...@earthlink.net Subject: Re: When do I need to override hash? To: cocoa-dev cocoa-dev@lists.apple.com Date: Friday, 2009 August 21, 00:48 On 2009 Aug 20, at 22:05, Jeff Laing wrote: Without wanting to keep the thread going forever, can I just ask why we would presume this? In fact, if I were implementing NSDictionary I'd assume the reverse, that I was not allowed to assume that an objects hash would not change.. If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. The impression I get from all this is that * if you do want to change how you hash, you should pull objects out of the collections with the old hash and then add them back in using the new hash. * be careful when choosing a hash scheme; it has to be fast and it has to produce keys that minimize collisions and yet come out the same when you want it to come out the same. ___ 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
Re: When do I need to override hash?
From the docs: If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by thehash method of the object must not change while the object is in the collection. Therefore, either the hash method must not rely on any of the object’s internal state information or you must make sure the object’s internal state information does not change while the object is in the collection. That's pretty hard to deal with. Returning 0 is certainly simpler :p -- Seth Willits ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote:
Returning 0 is certainly simpler :p
It is, but you can generally do better than just returning 0, usually
by just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
This satisfies the condition of hash (two equal objects will have the
same hash code) without relying on object state (since a particular
object's location in memory will never change). You can probably do
even better than this, but as with hash codes in general there is a
certain amount of experimentation required.
--
David Duncan
Apple DTS Animation and Printing
___
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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 12:33 PM, David Duncandavid.dun...@apple.com wrote:
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote:
Returning 0 is certainly simpler :p
It is, but you can generally do better than just returning 0, usually by
just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
This satisfies the condition of hash (two equal objects will have the same
hash code)
No it doesn't. Writing the hash method like that basically prevents
you from having an isEqual that does anything other than a pointer
comparison.
--
Clark S. Cox III
clarkc...@gmail.com
___
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
Re: When do I need to override hash?
Why do you say that? I haven't noticed any documented requirement that
ties the implementation details of -hash and -isEqual together.
- Bryan
Sent from my iPhone
On Aug 20, 2009, at 4:27 PM, Clark Cox clarkc...@gmail.com wrote:
On Thu, Aug 20, 2009 at 12:33 PM, David
Duncandavid.dun...@apple.com wrote:
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote:
Returning 0 is certainly simpler :p
It is, but you can generally do better than just returning 0,
usually by
just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
This satisfies the condition of hash (two equal objects will have
the same
hash code)
No it doesn't. Writing the hash method like that basically prevents
you from having an isEqual that does anything other than a pointer
comparison.
--
Clark S. Cox III
clarkc...@gmail.com
___
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/bryanhenry%40mac.com
This email sent to bryanhe...@mac.com
___
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
Re: When do I need to override hash?
-isEqual: is how Cocoa collections define equality. Saying that two
objects are equal means, by definition, that -[obj1 isEqual: obj2]
returns true.
On Thu, Aug 20, 2009 at 1:30 PM, Bryan Henrybryanhe...@mac.com wrote:
Why do you say that? I haven't noticed any documented requirement that ties
the implementation details of -hash and -isEqual together.
- Bryan
Sent from my iPhone
On Aug 20, 2009, at 4:27 PM, Clark Cox clarkc...@gmail.com wrote:
On Thu, Aug 20, 2009 at 12:33 PM, David Duncandavid.dun...@apple.com
wrote:
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote:
Returning 0 is certainly simpler :p
It is, but you can generally do better than just returning 0, usually by
just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
This satisfies the condition of hash (two equal objects will have the
same
hash code)
No it doesn't. Writing the hash method like that basically prevents
you from having an isEqual that does anything other than a pointer
comparison.
--
Clark S. Cox III
clarkc...@gmail.com
___
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/bryanhenry%40mac.com
This email sent to bryanhe...@mac.com
--
Clark S. Cox III
clarkc...@gmail.com
___
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
Re: When do I need to override hash?
From
http://developer.apple.com/documentation/Cocoa/Reference/Foundation/Protocols/NSObject_Protocol/Reference/NSObject.html#//apple_ref/occ/intfm/NSObject/hash
If two objects are equal (as determined by the isEqual: method), they
must have the same hash value. This last point is particularly
important if you define hash in a subclass and intend to put instances
of that subclass into a collection.
On Thu, Aug 20, 2009 at 1:30 PM, Bryan Henrybryanhe...@mac.com wrote:
Why do you say that? I haven't noticed any documented requirement that ties
the implementation details of -hash and -isEqual together.
- Bryan
Sent from my iPhone
On Aug 20, 2009, at 4:27 PM, Clark Cox clarkc...@gmail.com wrote:
On Thu, Aug 20, 2009 at 12:33 PM, David Duncandavid.dun...@apple.com
wrote:
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote:
Returning 0 is certainly simpler :p
It is, but you can generally do better than just returning 0, usually by
just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
This satisfies the condition of hash (two equal objects will have the
same
hash code)
No it doesn't. Writing the hash method like that basically prevents
you from having an isEqual that does anything other than a pointer
comparison.
--
Clark S. Cox III
clarkc...@gmail.com
___
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/bryanhenry%40mac.com
This email sent to bryanhe...@mac.com
--
Clark S. Cox III
clarkc...@gmail.com
___
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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 1:33 PM, Clark Coxclarkc...@gmail.com wrote: -isEqual: is how Cocoa collections define equality. Saying that two objects are equal means, by definition, that -[obj1 isEqual: obj2] returns true. This has nothing to do with -hash. P: Two objects are equal. Q: They have the same hash. P - Q. Note that Q does not imply P. --Kyle Sluder ___ 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
Re: When do I need to override hash?
Yes, but the problem with a hash based on the pointer is that it limits your isEqual implemenation from being based on anything more than the pointer, or you violate the If objects are equal, they must have the same hash rule. (Earlier email was a brain fart on my part.) - Bryan Sent from my iPhone On Aug 20, 2009, at 4:37 PM, Kyle Sluder kyle.slu...@gmail.com wrote: On Thu, Aug 20, 2009 at 1:33 PM, Clark Coxclarkc...@gmail.com wrote: -isEqual: is how Cocoa collections define equality. Saying that two objects are equal means, by definition, that -[obj1 isEqual: obj2] returns true. This has nothing to do with -hash. P: Two objects are equal. Q: They have the same hash. P - Q. Note that Q does not imply P. --Kyle Sluder ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 1:37 PM, Kyle Sluderkyle.slu...@gmail.com wrote: P: Two objects are equal. Q: They have the same hash. P - Q. Note that Q does not imply P. Or said another way... If the hash of ObjectA is equal to the hash of ObjectB then ObjectA _could_ be equal to ObjectB. If their hash differ they cannot be equal. The use of a hash to do a quick reject of equality is common for stl collections, java collections, Cocoa collections, etc. -Shawn ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 1:37 PM, Kyle Sluderkyle.slu...@gmail.com wrote: On Thu, Aug 20, 2009 at 1:33 PM, Clark Coxclarkc...@gmail.com wrote: -isEqual: is how Cocoa collections define equality. Saying that two objects are equal means, by definition, that -[obj1 isEqual: obj2] returns true. This has nothing to do with -hash. P: Two objects are equal. Q: They have the same hash. P - Q. Note that Q does not imply P. So, tell me how you can have two equal objects meet that condition, when the hash is based on the pointer value of self. -- Clark S. Cox III clarkc...@gmail.com ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 1:47 PM, Shawn Ericksonshaw...@gmail.com wrote: On Thu, Aug 20, 2009 at 1:37 PM, Kyle Sluderkyle.slu...@gmail.com wrote: P: Two objects are equal. Q: They have the same hash. P - Q. Note that Q does not imply P. Or said another way... If the hash of ObjectA is equal to the hash of ObjectB then ObjectA _could_ be equal to ObjectB. If their hash differ they cannot be equal. The use of a hash to do a quick reject of equality is common for stl collections, java collections, Cocoa collections, etc. Yes, and two different objects will have different pointer values. If the hash is based on the pointer values, then two different objects cannot have the same hash, regardless of whether or not they are equal. Hence, that implementation of hash is broken for any object that does anything other than a pointer comparison in -isEqual:. -- Clark S. Cox III clarkc...@gmail.com ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 2:01 PM, Clark Coxclarkc...@gmail.com wrote: Yes, and two different objects will have different pointer values. If the hash is based on the pointer values, then two different objects cannot have the same hash, regardless of whether or not they are equal. Hence, that implementation of hash is broken for any object that does anything other than a pointer comparison in -isEqual:. I thought we were talking about -hash just returning zero? --Kyle Sluder ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 2:14 PM, Kyle Sluderkyle.slu...@gmail.com wrote:
On Thu, Aug 20, 2009 at 2:01 PM, Clark Coxclarkc...@gmail.com wrote:
Yes, and two different objects will have different pointer values. If
the hash is based on the pointer values, then two different objects
cannot have the same hash, regardless of whether or not they are
equal. Hence, that implementation of hash is broken for any object
that does anything other than a pointer comparison in -isEqual:.
I thought we were talking about -hash just returning zero?
--Kyle Sluder
No, we were talking about:
It is, but you can generally do better than just returning 0, usually by just
extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
--
Clark S. Cox III
clarkc...@gmail.com
___
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
Re: When do I need to override hash?
On Aug 20, 2009, at 12:00 PM, Seth Willits wrote: From the docs: If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by thehash method of the object must not change while the object is in the collection. Therefore, either the hash method must not rely on any of the object’s internal state information or you must make sure the object’s internal state information does not change while the object is in the collection. That's pretty hard to deal with. Returning 0 is certainly simpler :p Simpler, but slower. Performance of NSSet and NSDictionary in particular will drop dramatically if the -hash values of unequal keys are always the same. If two objects are -isEqual: to each other, then they MUST have the same -hash value. NSSet and NSDictionary will behave incorrectly if you do this wrong for their keys. If two objects are not -isEqual: to each other, then they SHOULD have different -hash values. They MAY have the same -hash value, but NSSet and NSDictionary will be slower if that happens too often. -- Greg Parker gpar...@apple.com Runtime Wrangler ___ 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
Re: When do I need to override hash?
On 20 Aug 2009, at 22:16, Clark Cox wrote: On Thu, Aug 20, 2009 at 2:14 PM, Kyle Sluderkyle.slu...@gmail.com wrote: On Thu, Aug 20, 2009 at 2:01 PM, Clark Coxclarkc...@gmail.com wrote: Yes, and two different objects will have different pointer values. If the hash is based on the pointer values, then two different objects cannot have the same hash, regardless of whether or not they are equal. Hence, that implementation of hash is broken for any object that does anything other than a pointer comparison in -isEqual:. I thought we were talking about -hash just returning zero? --Kyle Sluder No, we were talking about: OK, so this discussion is getting a little crazy :-) The -hash method is important for objects that are used as keys in associative collections. So the worry about the hash value changing when an object's properties are altered is a bit of a red herring, because you *aren't supposed to change keys in associative collections*. If you do that in just about *any* implementation, ObjC or otherwise, you'll get undefined behaviour. So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts), if you change a property that affects *either* -isEqualTo: *or* -hash, you need to remove the object before mutating it and then add it back again afterwards. The one other thing I'll note is that occasionally you might be using an object as a key where only *some* of its properties contribute towards -hash and -isEqualTo:. In that case, you can safely change any of the other non-contributing properties. 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
Re: When do I need to override hash?
Yup, and my mistake in the suggestion :). Probably juggling too many
balls int he air again today...
On Aug 20, 2009, at 2:16 PM, Clark Cox wrote:
I thought we were talking about -hash just returning zero?
--Kyle Sluder
No, we were talking about:
It is, but you can generally do better than just returning 0,
usually by just extracting some bits from 'self', ala
-(NSUInteger)hash
{
uintptr_t hash = (uintptr_t)self;
return (hash 4);
}
--
David Duncan
Apple DTS Animation and Printing
___
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
RE: When do I need to override hash?
OK, so this discussion is getting a little crazy :-) Agreed. The -hash method is important for objects that are used as keys in associative collections. [snip] So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts) ... Is there any way that you can tell that some higher-level technology you are using (CoreData?) is putting your objects into an NSSet? That's presumably a hidden implementation detail which you can't assume one way or the other with any safety? ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 2:31 PM, Alastair Houghton wrote: The -hash method is important for objects that are used as keys in associative collections. So the worry about the hash value changing when an object's properties are altered is a bit of a red herring, because you *aren't supposed to change keys in associative collections*. If you do that in just about *any* implementation, ObjC or otherwise, you'll get undefined behaviour. So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts), if you change a property that affects *either* -isEqualTo: *or* -hash, you need to remove the object before mutating it and then add it back again afterwards. The documentation, nor did many others' comments on this topic, make it clear that the mutability is only a problem for the *keys*. Others and the docs talk about (paraphrasing) putting an object into a collection, not using an object as a key in an associative collection. Here are the docs: If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. If I follow this sentence, it says that if I put a (mutable string) into a (dictionary), the value returned by the -hash method of (the string) must not change while it's in the collection. It does *not* say that the hash method of the *KEY* can't change, it says the hash value of the object stored in the collection. Now maybe this is worded really poorly, but I think this is where the confusion comes from. It seems to be in direct contradiction to what you're saying. If it were only an issue for keys, then this is, like you said, no big deal. If my reading of the documentation is correct, then it's a much more prevalent problem, as others seem to be saying. -- Seth Willits ___ 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
RE: When do I need to override hash?
The -hash method is important for objects that are used as keys in associative collections. [snip] So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts) ... Is there any way that you can tell that some higher-level technology you are using (CoreData?) is putting your objects into an NSSet? That's presumably a hidden implementation detail which you can't assume one way or the other with any safety? Core Data plays by the same rules as everyone else regarding -hash, - isEqual and Cocoa collection classes. Every pair of objects that return YES from -isEqual must return the same -hash result. Core Data doesn't use random objects as keys in dictionaries or sets for this reason. It's not that we don't trust you, but ... to prevent misunderstandings, all NSManagedObject subclasses are forbidden from overriding -hash and -isEqual. Since NSManagedObjects have very specific semantic meanings associated with -isEqual and [[self objectID] isEqual:] no good could come of it anyway. If you need to know whether or not another object has put your object into an NSDictionary, you're probably doing something wrong. Do you have a specific concern about Core Data using your objects ? - Ben ___ 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
RE: When do I need to override hash?
Core Data doesn't use random objects as keys in dictionaries or sets for this reason. It's not that we don't trust you, but ... to prevent misunderstandings, all NSManagedObject subclasses are forbidden from overriding -hash and -isEqual. I have to admit, I didn't know this bit but I see it in the developer library along with a bunch of others. If you need to know whether or not another object has put your object into an NSDictionary, you're probably doing something wrong. Do you have a specific concern about Core Data using your objects ? No, I guess the point I was trying to make was that this discussion seemed to have touched on if you put your objects into an NSSet then you'll need to be more careful about the implementation of -hash, etc. I was trying to point out that just because my application code doesn't go anywhere near NSSet, its conceivable (to me) that Core Data (for example) might be storing dirty objects in an NSSet behind your back. So you can't not implement -hash, etc properly and hope everything will work. There may be any number of external technologies (Core Data was just an example) that may be using your objects in ways you aren't expecting, and there's no future-proof way you can cut corners. ___ 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
Re: When do I need to override hash?
On Thu, Aug 20, 2009 at 9:09 PM, Jeff Laingjeff.la...@spatialinfo.com wrote:
Core Data doesn't use random objects as keys in dictionaries or sets
for this reason. It's not that we don't trust you, but ... to
prevent misunderstandings, all NSManagedObject subclasses are
forbidden from overriding -hash and -isEqual.
I have to admit, I didn't know this bit but I see it in the developer library
along with a bunch of others.
If you need to know whether or not another object has put your object
into an NSDictionary, you're probably doing something wrong. Do you
have a specific concern about Core Data using your objects ?
No, I guess the point I was trying to make was that this discussion seemed to
have touched on if you put your objects into an NSSet then you'll need to be
more careful about the implementation of -hash, etc. I was trying to point
out that just because my application code doesn't go anywhere near NSSet, its
conceivable (to me) that Core Data (for example) might be storing dirty
objects in an NSSet behind your back. So you can't not implement -hash,
etc properly and hope everything will work.
The solution is simple:
If you implement -hash, you must implement -isEqual:
If you implement -isEqual:, you must implement -hash
If -isEqual: returns true for two given objects, those objects must
return the same value for -hash
If you don't implement either, NSObject's implementations are fine
also. i.e. NSObjects implementations are basically:
-(NSUInteger)hash { return (NSUInteger) self; }
-(BOOL)isEqual:(id)obj { return self == obj; }
--
Clark S. Cox III
clarkc...@gmail.com
___
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
Re: When do I need to override hash?
On Aug 20, 2009, at 20:51, Seth Willits wrote: On Aug 20, 2009, at 2:31 PM, Alastair Houghton wrote: The -hash method is important for objects that are used as keys in associative collections. So the worry about the hash value changing when an object's properties are altered is a bit of a red herring, because you *aren't supposed to change keys in associative collections*. If you do that in just about *any* implementation, ObjC or otherwise, you'll get undefined behaviour. So, in practice, it's perfectly safe in 99.9% of cases to base your hash off your object's properties. In the specific case when you're mutating objects that are keys in associative collections (NSDictionary and NSSet being the primary examples, along with their CoreFoundation counterparts), if you change a property that affects *either* -isEqualTo: *or* -hash, you need to remove the object before mutating it and then add it back again afterwards. The documentation, nor did many others' comments on this topic, make it clear that the mutability is only a problem for the *keys*. Others and the docs talk about (paraphrasing) putting an object into a collection, not using an object as a key in an associative collection. Yes. I believe Alastair misspoke. What he said is actually 99.9% true, but establishes a different point. The keys in a dictionary (or other keyed collection, like a map table) need to be immutable objects, but that's unrelated to the hash. Mutability in the keys would be bad, hash or no hash. Separately, keyed collections use isEqual: on the keys to determine equality, so they need the isEqual:/hash to follow the rules. (Because the rules imply they can short-circuit some potentially expensive isEqual: invocations by trying fast hash comparison first. Whether they do that is an implementation detail we don't know.) Separately, keyed collections may (and presumably do) use *key* hash values to distribute object values in memory. (Presumably, the key hashes may also be used to distribute key values in memory. That's an implementation detail we don't know.) Separately, collections use isEqual: on the object values to determine equality, when they care. (I doubt that NSDictionary cares about object value equality, but NSSet certainly does, as does NSArray, when asked to compare objects.) Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) So object values must also follow the isEqual:/hash rules. So AFAIK your reading of the documentation is absolutely correct. Object values cannot be mutated while in a collection, unless their hash value doesn't depend on the mutated properties. Key values cannot be mutated while used in a collection, period. [Actually, for all I know, key values *can* be mutated while used in a collection, provided the hash value doesn't change, but even if it technically feasible it sounds so un-useful I'd argue it's better just to assert that it's not allowed.] As far as the rest of this thread is concerned, I'd suggest we pay attention to what Clark Cox has said and ignore everything else. Of all our posts here today, he's the only one who's been *both* correct *and* brief simultaneously. :) ___ 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
RE: When do I need to override hash?
Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) Without wanting to keep the thread going forever, can I just ask why we would presume this? In fact, if I were implementing NSDictionary I'd assume the reverse, that I was not allowed to assume that an objects hash would not change. Is there some documentation on this restriction on the types of objects that can be put into an NSDictionary? I can see the NSSet dictates that objects must implement hash and isEqual: but NSDictionary only says that internally a dictionary uses a hash table - there are limits on the keys, which must conform to NSCopying,etc but I can't see anything about the values. Surely using an NSSet as bucket storage, for all objects whose keys hash to the same value, would add additional restrictions to NSDictionary that should be documented? ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 9:44 PM, Quincey Morris wrote: The keys in a dictionary (or other keyed collection, like a map table) need to be immutable objects, but that's unrelated to the hash. Mutability in the keys would be bad, hash or no hash. What do you mean by immutable? You can put a mutable object in a hashing collection as long as its -hash and -isEqual: do not depend on mutable state. For instance, if you configure a CFDictionary to use pointer equality and hash for its keys, you can use an NSMutableString as a key. [...] Separately, collections use isEqual: on the object values to determine equality, when they care. (I doubt that NSDictionary cares about object value equality, but NSSet certainly does, as does NSArray, when asked to compare objects.) Separately, collections may (and presumably sometimes do) use *object* hash values to distribute objects in memory. (Obviously, NSSet does, and for all we know NSDictionary does too, to distribute object values that stored under the same key hash value -- though it would be an implementation detail.) I use NSMutableStrings as values (not keys) in NSDictionary and expect that to work, even though hash/isEqual: of those strings is certainly changing while in the collection. CFDictionary at least doesn't include a hash function in its value callback, although it does require an equality function. From my quick look at the source, the only place that equality callback is used is in testing CFEqual(dict1, dict2), CFDictionaryGetCountOfValue(), and CFDictionaryContainsValue(). smime.p7s Description: S/MIME cryptographic signature ___ 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
Re: When do I need to override hash?
On Aug 20, 2009, at 22:05, Jeff Laing wrote: Without wanting to keep the thread going forever, can I just ask why we would presume this? In fact, if I were implementing NSDictionary I'd assume the reverse, that I was not allowed to assume that an objects hash would not change. Is there some documentation on this restriction on the types of objects that can be put into an NSDictionary? Seth explicitly quoted the documentation of this restriction in the post to which I replied: (This is from the documentation for 'hash'.) If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. It is absolutely possible that NSDictionary does not use hash values to determine the object's position in the collection and so would be exempt from the above restriction. It's also possible (maybe even likely) that NSArray doesn't use hash values to determine the object's position in the collection. So, now that you mention it, I guess we don't know for sure which collections do and do not depend on hash values for this purpose. (It's certainly conceivable that both NSDictionary and NSArray do use object hash values to manage their internal storage, perhaps only for very large collections.) Sounds like something that ought to be documented explicitly somewhere. In practice, it's not of general concern, because it doesn't seem generally useful to have objects that are safely collectable only in certain kinds of collections. For those specific cases where you had mutable objects with unstable hash values, you'd have to choose and bet on your interpretation of which collections it was safe to use. ___ 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
Re: When do I need to override hash?
On Wed, Aug 19, 2009 at 4:28 PM, Gideon Kinggid...@novamind.com wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? You need to override -hash for the simple reason that the documentation says you need to override -hash. That gives anyone else license to assume you implement -hash if you implement -isEqual. As for computing the hash itself, only you can answer that. The naïve option is to just return your self pointer, but that's not going to work well. --Kyle Sluder ___ 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
Re: When do I need to override hash?
On Aug 19, 2009, at 4:28 PM, Gideon King wrote:
So do I need to override hash too? If so, are there any
recommendations as to how to determine the hash easily?
If you need to override -isEqual: to provide something besides pointer
comparison, you should also override -hash. If objects are equal,
their hashes must be equal or you may trigger undefined behaviour in
who knows what situations.
While this may not offer the best performance, the easiest way to
implement -hash would be to take all the properties/internal state of
your object that affect equality, format them into an NSString, and
then return the hash of the string.
E.g.:
- (NSUInteger)hash {
NSString* valueRepresentation = [NSString stringWithFormat:@%@ %lu,
self.companyName,
self.departmentID];
return [valueRepresentation hash];
}
hope this helps,
-natevw
___
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
Re: When do I need to override hash?
On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? Sorry, just came across this thread that has some more tips: http://www.omnigroup.com/mailman/archive/macosx-dev/2003-December/049844.html If you need better performance from your hash function than my previous suggestion, you can just pick a somewhat unique property and return its -hash. This works because, while equal object have equal hashes, equal hashes don't guarantee equality. -nvw ___ 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
Re: When do I need to override hash?
Excellent, thanks for that - in my case I only have up to about a dozen objects in my array, so I'll just return 0 for the hash and let it fall back to isEqual:. I see that some of the Omni classes do that too... In other cases where I make few changes but do lots of comparisons, I might use the string hash idea and cache the return value in the object, triggering an update whenever the relevant data changes. This would be easy for me because the objects in question can archive themselves to XML and I could use the XML string. Gideon On 20/08/2009, at 10:58 AM, Nathan Vander Wilt wrote: On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? Sorry, just came across this thread that has some more tips: http://www.omnigroup.com/mailman/archive/macosx-dev/2003-December/049844.html If you need better performance from your hash function than my previous suggestion, you can just pick a somewhat unique property and return its -hash. This works because, while equal object have equal hashes, equal hashes don't guarantee equality. -nvw ___ 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
Re: When do I need to override hash?
On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? I probably shouldn't admit this, but I've yet to override hash and have yet to notice any problems. The docs say I should, so I realize I likely should, but I would really like a concrete reason to do so. I've never called hash, nor seen it ever called by anyone else's code. I assume the frameworks call it from somewhere, but where? -- Seth Willits ___ 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
Re: When do I need to override hash?
I see your point, and I have been writing Obj-C code since 1991 and
don't recall ever having written a hash method, and it's never bitten
me before.
...but I believe Kyle's point is very valid. The documentation is very
explicitly saying that you should implement it, so if you don't then
you can't complain when they change their implementation to use the
hash value and all your stuff breaks. And of course, in many cases
using a hash value would be a very good performance optimization.
But having said that, if they did change the implementation of the
collection classes to use the hash values, then there would be a
massive amount of code broken.
For me, I'm quite happy to just add a method:
- (NSUInteger)hash {
return 0; // Force the caller to call the isEqual: method to actually
determine equality.
}
to all my classes that implement isEqual: and thus apply by the
(seemingly unenforced) law.
Gideon
On 20/08/2009, at 11:19 AM, Seth Willits wrote:
I probably shouldn't admit this, but I've yet to override hash and
have yet to notice any problems. The docs say I should, so I realize
I likely should, but I would really like a concrete reason to do so.
I've never called hash, nor seen it ever called by anyone else's
code. I assume the frameworks call it from somewhere, but where?
___
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
Re: When do I need to override hash?
On Aug 19, 2009, at 6:19 PM, Seth Willits wrote: On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? I probably shouldn't admit this, but I've yet to override hash and have yet to notice any problems. The docs say I should, so I realize I likely should, but I would really like a concrete reason to do so. I've never called hash, nor seen it ever called by anyone else's code. I assume the frameworks call it from somewhere, but where? NSDictionary, NSSet, NSHashTable, NSMapTable, and possibly other classes all use hash. So if you ever put your objects in an NSSet or use them as dictionary keys, -hash should be called at some point. smime.p7s Description: S/MIME cryptographic signature ___ 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
Re: When do I need to override hash?
Seth Willits wrote: On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? I probably shouldn't admit this, but I've yet to override hash and have yet to notice any problems. The docs say I should, so I realize I likely should, but I would really like a concrete reason to do so. I've never called hash, nor seen it ever called by anyone else's code. I assume the frameworks call it from somewhere, but where? When it sticks things in any kind of hashtable or wants for some reason a way to partition objects roughly to cut down the number of comparisons it has to do on them. So it's very important that if two objects are isEqual: to each other, they must have the same hash. Else what could happen is you insert one into any of the collections which use hash to bucket the objects, then you put another one in which isEqual: to the first. If it has a different hash (as it's not supposed to do), the code will go look in the wrong bucket, won't find the object you put there earlier and then you'll have two objects in the collection which are isEqual: to each other. ___ 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
Re: When do I need to override hash?
On Wed, Aug 19, 2009 at 6:19 PM, Seth Willitssli...@araelium.com wrote: On Aug 19, 2009, at 4:28 PM, Gideon King wrote: So do I need to override hash too? If so, are there any recommendations as to how to determine the hash easily? I probably shouldn't admit this, but I've yet to override hash and have yet to notice any problems. The docs say I should, so I realize I likely should, but I would really like a concrete reason to do so. I've never called hash, nor seen it ever called by anyone else's code. I assume the frameworks call it from somewhere, but where? If you've ever put those objects in an associative or hashing container (NSSet, NSDictionary keys, NSHashMap NSHashTable, etc.), you're probably sitting on obscure, hard to find bugs. In general, if you override -isEqual:, you should override -hash. Period. -- Clark S. Cox III clarkc...@gmail.com ___ 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
Re: When do I need to override hash?
On Aug 19, 2009, at 6:17 PM, Gideon King wrote: In other cases where I make few changes but do lots of comparisons, I might use the string hash idea and cache the return value in the object, triggering an update whenever the relevant data changes. This would be easy for me because the objects in question can archive themselves to XML and I could use the XML string. Note that you must not change the hash of an object while it is in a hashing collection; this causes bugs that can be really hard to track down (I learned the hard way). See this article, specifically the note on The mutable pitfall. http://www.mulle-kybernetik.com/artikel/Optimization/opti-7.html Some of the comments on Apple's implementation are likely dated, but it's still good background reading. smime.p7s Description: S/MIME cryptographic signature ___ 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
