Best practices for overriding isEqual: and hash

Question

How do you properly override isEqual: in Objective-C? The "catch" seems to be that if two objects are equal (as determined by the isEqual: method), they must have the same hash value.

The Introspection section of the Cocoa Fundamentals Guide does have an example on how to override isEqual:, copied as follows, for a class named MyWidget:

- (BOOL)isEqual:(id)other {     if (other == self)         return YES;     if (!other || ![other isKindOfClass:[self class]])         return NO;     return [self isEqualToWidget:other]; }  - (BOOL)isEqualToWidget:(MyWidget *)aWidget {     if (self == aWidget)         return YES;     if (![(id)[self name] isEqual:[aWidget name]])         return NO;     if (![[self data] isEqualToData:[aWidget data]])         return NO;     return YES; } 

It checks pointer equality, then class equality, and finally compares the objects using isEqualToWidget:, which only checks the name and data properties. What the example doesn't show is how to override hash.

Let's assume there are other properties that do not affect equality, say age. Shouldn't the hash method be overridden such that only name and data affect the hash? And if so, how would you do that? Just add the hashes of name and data? For example:

- (NSUInteger)hash {     NSUInteger hash = 0;     hash += [[self name] hash];     hash += [[self data] hash];     return hash; } 

Is that sufficient? Is there a better technique? What if you have primitives, like int? Convert them to NSNumber to get their hash? Or structs like NSRect?

(Brain fart: Originally wrote "bitwise OR" them together with |=. Meant add.)

Answer 1

Start with

 NSUInteger prime = 31;  NSUInteger result = 1; 

Then for every primitive you do

 result = prime * result + var 

For objects you use 0 for nil and otherwise their hashcode.

 result = prime * result + [var hash]; 

For booleans you use two different values

 result = prime * result + ((var)?1231:1237); 

---

Explanation and Attribution

This is not tcurdt's work, and comments were asking for more explanation, so I believe an edit for attribution is fair.

This algorithm was popularized in the book "Effective Java", and the relevant chapter can currently be found online here. That book popularized the algorithm, which is now a default in a number of Java applications (including Eclipse). It derived, however, from an even older implementation which is variously attributed to Dan Bernstein or Chris Torek. That older algorithm originally floated around on Usenet, and certain attribution is difficult. For example, there is some interesting commentary in this Apache code (search for their names) that references the original source.

Bottom line is, this is a very old, simple hashing algorithm. It is not the most performant, and it is not even proven mathematically to be a "good" algorithm. But it is simple, and a lot of people have used it for a long time with good results, so it has a lot of historical support.