CODEWITHSUNDEEP
objective-ccocoaequalitynsobject
Aleksa Topić
Aleksa Topić

Reputation: 549

Why must two equal objects have same hash value?

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?

Upvotes: 2

Views: 485

Answers (2)

Jon Hess
Jon Hess

Reputation: 14247

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.

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1500335

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.

Upvotes: 8

Related Questions