Re: NSDictionary design bug (was: Re: Ugly bug in Foundation, beware!)
Re: NSDictionary design bug (was: Re: Ugly bug in Foundation, beware!)
- Subject: Re: NSDictionary design bug (was: Re: Ugly bug in Foundation, beware!)
- From: Shawn Erickson <email@hidden>
- Date: Sun, 6 Jun 2004 12:16:49 -0700
On Jun 6, 2004, at 8:00 AM, Marcel Weiher wrote:
As the copy will satisfy the -hash and -isEqual "identity", the copy
is just as good as the original for the purpose.
If there is one "invariant" a dictionary should obey, it is that the
following must hold:
[dict setObject:b forKey:a];
b == [dict objectForKey:a];
NSDictionary does not obey this invariant. I have created a little
test program to make this more clear. We create an NSObject subclass
that faithfully implements the NSCopying protocol as documented. We
can use objects of this class as keys to our dictionary, but we can
never get the objects back out again, even using the exact same key!!
It also faithfully implements the recommendation for "hash", and yet
it breaks...
Did you implement an isEqual and hash that can equate two distinct
instances of matching keys? Yes dictionary isn't friendly to
isEqual/hash that are based on reference equality (the default
implementation), unless you do this or you retain instead of copy. If
your key is immutable (not sure if it is or not) they why are you
creating a new copy, add a retain instead and return self. That would
solve this problem if you don't want to implement the required
hash/isEqual methods. If not consider...
Java's HashMap (near equivalent to NSMutableDictionary since they both
bucket things using hashes) doesn't copy the keys but simply references
them. This can introduce different issues, issues in many ways the flip
of what you are noting above but which can results in the same problem
and a much worse problem.
For example (say the Key class implements an non-reference based
hashCode and equals)...
key.setValue("foo");
map.put(key, value);
...
key.setValue("bar");
...
value = map.get(key)
In the above value will not be found (which may or may not be want you
want). Also note the key originally used for the value now no longer
relates to the value as it was originally put into the collection yet
it is still referenced by the map as being related to that value (which
may or may not be want you want). An additional twist, the ugly one
(and likely why NSDictionary does what it does), is if by luck the
changed key's hash happens to match the old key's hash then the map
will get a hit (it stores the hash it used to bucket the value) and
then it will attempt to compare the keys to make sure that they are the
same (using equals) however since the key referenced by the map is the
same key (by reference) as the one being using in get then they will
always match yet the keys are likely in intent different (the original
key used to put in the value and the current version of key contained
different data). So you can get a false hit and the wrong value back.
The funny thing is I had to fix this very issue today in a object
lookup cache that someone put into our product since the keys used in
the cache happened to get reused and hence changed after the fact. The
keys got reused because they themselves happened to put into and gotten
from a different unrelated cache based on the key size (buffer size)
not on its contents (this cache was the newly added code that caused
the problem in the other object cache).
So both have issues and in the non-copy case you have a potentially
ugly issue that is not easy to solve without likely reverting to
copying the key being used, a copy for exclusive use of the map.
-Shawn
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.
| References: | |
| | >Ugly bug in Foundation, beware! (From: Ondra Cada <email@hidden>) |
| | >Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Alastair Houghton <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Ondra Cada <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Alastair Houghton <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Brent Gulanowski <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Alastair Houghton <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Ondra Cada <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Marcel Weiher <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Brent Gulanowski <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: "Louis C. Sacha" <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Marcel Weiher <email@hidden>) |
| | >Re: Is that really a bug at all? (was: Re: Ugly bug in Foundation, beware!) (From: Nat! <email@hidden>) |
| | >Re: NSDictionary design bug (was: Re: Ugly bug in Foundation, beware!) (From: Marcel Weiher <email@hidden>) |