6

Say I have an object called Person which has the property socialSecurityNumber, and this class overrides the isEqual: method to return true when the social security number properties are equal. And say I've put a bunch of instances of Person into an NSDictionary.

If I now instantiate a newPerson object which happens to have the same social security number as one already in the dictionary, and I do [myDictionary objectForKey:newPerson], will it use the isEqual: and return YES, or will it compare pointers and return NO?

I know I can write a simple test to find out, but I want to understand how exactly objectForKey: finds a match in a dictionary, and generally how consistent this is across Cocoa (i.e. does NSArray's indexofObject: work the same?)

lmirosevic
  • 15,787
  • 13
  • 70
  • 116

2 Answers2

11

NSDictionary works like a hashtable. So it uses both -hash and -isEqual: to find the object in the dictionary corresponding to the given key.

So to answer your question for NSDictionary, this uses isEqual: and not pointer comparison. But you also should implement hash in addition to isEqual: on your Person class for this to work.

A key-value pair within a dictionary is called an entry. Each entry consists of one object that represents the key and a second object that is that key’s value. Within a dictionary, the keys are unique. That is, no two keys in a single dictionary are equal (as determined by isEqual:).

If two objects are equal, they must have the same hash value. This last point is particularly important if you define isEqual: in a subclass and intend to put instances of that subclass into a collection. Make sure you also define hash in your subclass.

Starting at index 0, each element of the array is sent an isEqual: message until a match is found or the end of the array is reached. This method passes the anObject parameter to each isEqual: message. Objects are considered equal if isEqual: (declared in the NSObject protocol) returns YES.

You should always read the documentation : as pointed out by the extracts quoted above, these kind of details are often explained in the "Discussion" or "Special Consideration" sections of the method documentation or in the "Overview" section of the class documentation itself.

AliSoftware
  • 32,623
  • 6
  • 82
  • 77
  • As you like as long as 2 objets that are equal have the same hash, and that the hash is not too complex to compute. The algorithm used for that is up to you, but two objects with different hash values will always be considered different, and two objets with the same hash value will be considered to be likely equal, and will call `isEqual:` to make sure they are truly equal indeed. This allows very fast comparison and dictionary lookup by only comparing hash values (that are only integers), and only engage in a real comparison with `isEqual:` when hashes are equal. – AliSoftware Jun 28 '13 at 15:16
  • For example, for a string, one may implement the `hash` method by returning the length of the string. Two strings that are equal will have the same hash, and 2 different strings will have different hash values. Some strings that are different (like `@"bar"` and `@"baz"`) will still have the same hash value, but that's not a problem, in that case `isEqual:` will then make a deeper analysis character by character to check for equality. But this (more time-consuming) comparison will only be done to compare strings of the same length: string with different length will return `NO` more quickly. – AliSoftware Jun 28 '13 at 18:04
  • Note that one may also implement `hash` by always returning `0` for example: it still conforms to the requirements for a hash function, but as all objects will have the same hash, all the comparisons will trigger a call to `isEqual:`. Of course even if this will work, this would be a disaster in term of performance, as an in-depth comparison will be done each time in that case. When implementing `hash`, everything is a matter of compromises, between a hash that is simple to compute but will also distribute various hash values evenly for different objects, to take advantage of this mechanism. – AliSoftware Jun 28 '13 at 18:13
  • Awesome explanation, thanks for that. But which method should I override to implement hash check? – Raj Pawan Gumdal Jun 29 '13 at 15:48
  • 1
    The `hash` method, as stated in the documentation. – AliSoftware Jun 29 '13 at 20:49
  • You just saved my day since none if this information was mentioned in the documentation on `objectForKey:` – Jan Z. Feb 14 '23 at 16:43
1

how consistent this is across Cocoa (i.e. does NSArray's indexofObject: work the same?)

It is consistent and at the same time it isn't. What I mean is that there are two methods that could be used: isEqual and hash. You should not be too much concerned about which is used when. What you should instead focus on is to respect the NSObject protocol requirements and make sure that if two objects are equal according to isEqual they also have the same hash.

From the isEqual documentation in the NSObject Protocol Reference

If two objects are equal, they must have the same hash value. This last point is particularly important if you define isEqual: in a subclass and intend to put instances of that subclass into a collection. Make sure you also define hash in your subclass.

Analog File
  • 5,280
  • 20
  • 23
  • Two comments: One, NSArray has a second method "indexOfObjectIdenticalTo:" which finds the _same_ object, that is the same object pointer. Two different NSString* objects containing "foo" would be considered different. Two, the default implementation of hash and isEqual: uses the pointer as the hash key and compares pointers. For example NSWindow/UIWindow could be used as keys in a dictionary, and the pointers would have to be identical. – gnasher729 Mar 24 '14 at 01:21