NSObject Protocol Reference says "If two objects are equal, they must have the same hash value."
Why must? What could be the problem with two equal objects not having same hash value?
2 Answers
Then you wouldn't be able to look up equal values in a hash table, basically. Hash codes are basically used as a quick way of finding potential key matches within a hash table (or hash set). That relies on the "object equality implies hash equality" contract.
If you're not planning to use your objects within anything which uses hashing for quick lookup, you may well get away with having equal objects returning different hash codes - but I'd really avoid it if you can.
4 Comments
Aleksa Topić
So, it's not really a must? Like methods should return retained objects if methods only start with "init", "new" or "copy" (but don't have to). It is what is expected of my class.
Chuck
@Aleksa: It is as much as must as anything else in the world. A hash method that doesn't produce the same hash for objects considered equal is worthless and incorrect. It is a hash function's sine qua non.
Jon Skeet
@Chuck: On the other hand, if the hash method isn't going to be used, it won't hurt anything... but that's a big "if" and a maintenance nightmare waiting to happen, of course :)
Jeff Laing
And you don't know whether it will be used or not - you don't know how autorelease pools are implemented, you don't know that KVO isn't swizzling you behind the scenes, etc.
Here is a simplified description of how a hash table works. NSSet is a hash table.
The basic structure
Allocate an NSArray of N NSMutableArrays. Let's call the outer array "table" and the inner arrays "lists". This structure is our hash table.
How inserting works
To insert an object, call 'hash' on it. This gives us a number. Truncate the number to be between 0 and (N - 1). Treat that result as an index in table. Go to the mutable array at that slot (list), and see if 'object' is already in the list, if not add it. If so, nothing to do.
How lookup works
To see if a value is in the hash table, call hash on it. This gives us a number. Truncate the number to be between 0 and (N - 1). Treat that result as an index in table. Go to the mutable array at that slot (list), and see if 'object' is already in the list. If it's there, the table contains the object, otherwise it doesn't.
Why do equal objects have to have equal hash values?
The hash code is used to find which list to search. If two objects are conceptually equal but have different hash values, then when we go to do the look up above in the outer table we won't find the object in the expected list since our objects will resolve to two different lists.
