mikeash.com pyblog/friday-qa-2010-06-18-implementing-equality-and-hashing.html comments

Ilya Kulakov - 2019-05-24 20:46:03

Fri, 24 May 2019 20:46:03 GMT

Sandeep,

In the root class (or as an extension of NSObject) you could add the following method:



- (BOOL)isMostSpecializedEqual:(NSObject *)anObject

{

    if (anObject == self)

        return YES;



    NSObject *parent = nil;

    NSObject *child = nil;



    if ([self isKindOfClass:anObject.class])

    {

        parent = anObject;

        child = self;

    }

    else if ([anObject isKindOfClass:self.class])

    {

        parent = self;

        child = anObject;

    }

    else

        return NO;



    return [child isEqual:parent];

}

then implement -isEqual:



- (BOOL)isEqual:(id)anObject

{

    if (anObject == self)

        return YES;

    else if ([self isKindOfClass:anObject.class])

        // perform memberwise-equality checks

    else

        return [self SR_isMostSpecializedEqual:anObject]

}

This way of isEqual: of the most specialized class in the hierarchy will be consistently used.
So if at some point one of the subclasses will introduce a state change (e.g. additional property)
it's own isEqual: will consistently judge.

Sandeep Aggarwal - 2016-08-25 11:51:12

Thu, 25 Aug 2016 11:51:12 GMT

In the paragraph A Note on Subclassing you wrote at the end Rather than working around it with weird implementations of isEqual:, consider redesigning your class hierarchy.

What if, I want to keep the similar hierarchy as in this case which is not bad at all then how to deal with this transitivity problem?

Vince - 2014-04-27 14:00:57

Sun, 27 Apr 2014 14:00:57 GMT

For several years I've had my doubts about how others have explained or justified non-transitivity of equality with respect to sub-classes. The first paragraph of "A note on subclassing" has finally put that to rest. Thanks.

Chris - 2013-01-11 07:23:56

Fri, 11 Jan 2013 07:23:56 GMT

In the case one of the properties is allowed to be nil, this method is incomplete: when you have two objects of class A with a property p that is nil on both, [x.p isEqual:y.p] will return false. I also wrote about this here: http://chris.eidhof.nl/post/38065014421/implementing-value-objects-in-objective-c

mikeash - 2010-06-21 16:32:02

Mon, 21 Jun 2010 16:32:02 GMT

Note that it is impossible to have a hash table with 2^64 distinct values, because you'd run out of address space long beforehand. It's not even possible in theory, as long as your hash value integer is the same size as your pointers.

The problem is not when you actually have more than 2^64 live values, but when you have more than 2^64 possible values. Since it's impractical to alter your hash function in the middle of running your program, it's possible to find two objects with the same hash and have to deal with the collision, even when you have far fewer than 2^64 live values.

Derek - 2010-06-21 14:24:58

Mon, 21 Jun 2010 14:24:58 GMT

Trevor: The hash function only returns a NSUInteger, that means there are at max 64 bits of unique numbers there. A NSString can have more possible combinations than that (think of a hash table of 100 character strings). There MUST be some collisions if you have more than 2^64 distinct values stored in a hash table.

mikeash - 2010-06-20 14:38:12

Sun, 20 Jun 2010 14:38:12 GMT

Actually it's "completely" that applies here. You can avoid hash collisions for special cases, but you can't avoid them in all cases all of the time. Your hash table either has to be very special-purpose (as in the case of using a perfect hash because you know all of the keys in advance) or it needs to be able to handle collisions.

Trevor - 2010-06-20 05:08:10

Sun, 20 Jun 2010 05:08:10 GMT

it's provably impossible to avoid it completely

Not sure what you mean by "impossible". If the keys are known in advance, a perfect hash avoids all collisions:

http://en.wikipedia.org/wiki/Perfect_hash_function

charles - 2010-06-19 18:45:30

Sat, 19 Jun 2010 18:45:30 GMT

Great point on NSSet: using mutable objects in an NSSet is probably the most likely thing that one could do without realizing (at least for NSDictionary, the key is copied, so even mutable objects will be made immutable). At least I had never thought of that issue.

Erik - 2010-06-19 18:16:59

Sat, 19 Jun 2010 18:16:59 GMT

You can use mutable objects in an NSSet as long as you implement the hash method such that the value it returns is not based on the mutable properties. An example of this would be if you had mutable objects that have an immutable primary key such as a GUID or sone other identifier. You can even just use the pointer value if instance identity is sufficient. Obviously this is something that you have to decide whether or not is appropriate for your your design; it would allow you to insert another "equivalent" object into the set which may or may not be "correct".

mikeash - 2010-06-19 17:58:04

Sat, 19 Jun 2010 17:58:04 GMT

For holding mutable, mutated objects, use an NSArray. Performance will suffer, but that's probably true of any collection holding changing objects.

Jeff Johnson - 2010-06-19 17:25:40

Sat, 19 Jun 2010 17:25:40 GMT

Mike, what about mutable objects in an NSSet?

mikeash - 2010-06-19 15:00:57

Sat, 19 Jun 2010 15:00:57 GMT

Frederik: That is probably a good technique. Overall it can be hard to measure the effectiveness of this stuff. I tend to go with a good balance between ease of coding and whatever looks like it will do a good job of mixing up the bits.

André Pang: The part that says "or you must make sure the object's internal state information does not change while the object is in the collection" is key. It's usually much easier, and much better, to simply not mutate your mutable keys while they're being used as keys, than to try to figure out how to make their hash not depend on their mutable value. Mutating a key while it's in a collection is probably another code smell.

Regarding Unicode, looks like I broke it when I added comment previews. Should be fixed now.

Erik Price - 2010-06-19 13:29:01

Sat, 19 Jun 2010 13:29:01 GMT

Andre, yes - using mutable objects as dictionary keys is the path to madness (if the object can mutate while active as a dict key). That's one reason why people commonly use NSStrings or some other key that reasonably uniquely identifies an object as dictionary keys.

Andre Pang - 2010-06-19 08:38:51

Sat, 19 Jun 2010 08:38:51 GMT

Good article as always Mike, though you didn't answer one question that's always bugged me. The Cocoa docs on -[NSObject hash] says this:

http://developer.apple.com/mac/library/documentation/cocoa/reference/foundation/Protocols/NSObject_Protocol/Reference/NSObject.html#//apple_ref/occ/intfm/NSObject/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. 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. Thus, for example, a mutable dictionary can be put in a hash table but you must not change it while it is in there. (Note that it can be difficult to know whether or not a given object is in a collection.)"

Well, umm. If the hash method cannot rely on any of the object's internal state that _may_ change throughout it's lifetime, this means that writing -hash for mutable objects becomes far more intricate. (I know why the restriction's there; presumably it's one of the reasons why NSDictionary copies its keys rather than simply retaining them. Dunno about NSMapTable though.)

I took a very braindead approach for RMModelObject's -hash method (sum the pointers for all of the object's ivars) because I felt it was the only safe way to keep within the Cocoa spec that'd still generate somewhat useful hash values.

Thoughts?

P.S. Your commenting doesn't support unicode? It doesn't like the e-acute in my name :).

Frederik - 2010-06-19 06:50:11

Sat, 19 Jun 2010 06:50:11 GMT

Thanks for choosing a great topic, and a great article! I followed the advice at http://stackoverflow.com/questions/254281/ to implement my hash methods, using a prime number (31) to multiply each component of the hash before addition. What are your thoughts on that?

Also, adding boolean variables to a hash is needed quite often. The article suggests (var) ? 1231 : 1237 for those.

Adam Maxwell - 2010-06-19 05:02:35

Sat, 19 Jun 2010 05:02:35 GMT

Nice article, and one that I wish I'd had a few years ago. Another useful article is at http://www.mulle-kybernetik.com/artikel/Optimization/opti-7.html (although slightly dated). I implemented -hash and -isEqual: improperly once upon a time, and it led to random crashes under very hard-to-reproduce circumstances. These are definitely worth getting right!

Prior to Snow Leopard, CFURL was also terrible in a hashing collection because it would end up copying and manipulating strings each time the hash function was called. It looks like it's computed once and stored inline, now, which should be much better for performance.

mikeash - 2010-06-19 03:37:14

Sat, 19 Jun 2010 03:37:14 GMT

Ahruman: A fine point. And if you need a better hashing algorithm but don't feel like overriding what Cocoa does universally, you may benefit from custom callbacks in an NSMapTable or NSHashTable as detailed in my previous post:

http://www.mikeash.com/pyblog/friday-qa-2010-05-28-leopard-collection-classes.html

Anonymous: In general, my trust of a system is inversely proportional to my knowledge of a system. Some key exceptions are GCD and libc, but even those aren't as solid as I'd like.

Anonymous - 2010-06-18 16:05:25

Fri, 18 Jun 2010 16:05:25 GMT

Ahruman: this is some fascinating info, and this combined with a growing collection of other observations about Cocoa on Mike's blog is really starting to erode my confidence in the robustness and stability of the Cocoa frameworks... :/

Ahruman - 2010-06-18 15:52:29

Fri, 18 Jun 2010 15:52:29 GMT

A related pitfall: it's easy to assume that the basic Foundation types will have good, general -hash implementations, but in fact they don't. For the collection types, -hash is equal to -count.

There are good reasons for this, but it's a potentially major pitfall. Concretely, in a recent case that involved uniquing several million short arrays, I reduced runtime from over twelve hours to eleven seconds by noticing this and implementing custom hashing and comparison.

Another fascinatin' anecdote: prior to Snow Leopard, the -hash value of boolean NSNumbers did not match that of integer NSNumbers with value 0 and 1, but -isEqual: claimed they were equal.