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

Reply via email to