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: Quincey Morris <email@hidden>
- Date: Thu, 20 Aug 2009 23:11:51 -0700
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 (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