2

When we use a custom object as NSDictionary's key, we need to make sure the custom object conforms to "NSCopying" protocol, implement "isEqual" and "hash". Otherwise, there would be something wrong. In this wonderful article: http://www.objc.io/issue-7/value-objects.html, it indicated that it may have very bad performance issue.

let’s have a look at what happens when we don’t have a hash function, and we try to use Person objects as keys in a dictionary:

NSMutableDictionary* dictionary = [NSMutableDictionary dictionary];
NSDate* start = [NSDate date];
for (int i = 0; i < 50000; i++) {
    NSString* name = randomString();
    Person* p = [[Person alloc] initWithName:name birthDate:[NSDate date] numberOfKids:i++];
    [dictionary setObject:@"value" forKey:p];
}
NSLog(@"%f", [[NSDate date] timeIntervalSinceDate:start]);

This takes 29 seconds on my machine. In comparison, when we implement a basic hash function, the same code runs in 0.4 seconds. These are not proper benchmarks, but do give a very good indication of why it’s important to implement a proper hash function.

I know it is wrong if we do not provide hash function for the custom object. But why it has so big performance problem? As I know, if we do not implement hash function, custom object will use pointer as its hash. pointer is unique, so it is perfect hash if only consider performance issue.

Then I tried similar code on NSMutableSet instead of NSMutableDictionary and get opposite result. Use default hash function will run faster, why?

Dollar Zhang
  • 53
  • 5
  • Is it intended that you have `i` as for-counter and use `i++` inside the loop? – qwerty_so Apr 21 '15 at 09:07
  • @ThomasKilian Thanks for pointing that out. Just copy the code from the article. Not intended to use i++ inside the loop – Dollar Zhang Apr 21 '15 at 09:19
  • Memory allocation on iOS is 16-byte aligned so pointers might not make great hash values. Not a duplicate but possibly helpful: http://stackoverflow.com/questions/3442639/hashing-of-pointer-values – samgak Apr 21 '15 at 09:25
  • Not having a real idea but isn't the hash simply calculated by taking the object address in all cases? – qwerty_so Apr 21 '15 at 09:56

0 Answers0