Override hash value of NSArray

Question

This SO answer shows that the hash of an NSDictionary is the number of entries in the dictionary. (Similarly, the hash of an NSArray is its length.) The answer goes on to suggest creating a category to provide a better hash implementation.

If you need to have a more accurate hash value, you can provide one yourself in an Obj-C category.

But when I try this, it appears to use the original hash implementation anyway.

We have the header in NSDictionary+Hash.h

#import <Foundation/Foundation.h>

@interface NSDictionary (Hash)
- (NSUInteger)hash;
@end

And the implementation in NSDictionary+Hash.m:

#import "NSDictionary+Hash.h"

@implementation NSDictionary (Hash)

- (NSUInteger)hash
{
    // Based upon standard hash algorithm ~ https://stackoverflow.com/a/4393493/337735
    NSUInteger result = 1;
    NSUInteger prime = 31;
    // Fast enumeration has an unstable ordering, so explicitly sort the keys
    // https://stackoverflow.com/a/8529761/337735
    for (id key in [[self allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
        id value = [self objectForKey:key];
        // okay, so copying Java's hashCode a bit:
        // http://docs.oracle.com/javase/6/docs/api/java/util/Map.Entry.html#hashCode()
        result = prime * result + ([key hash] ^ [value hash]);
    }
    return result;
}

A simple unit test shows the original implementation is in use:

#import "NSDictionary+Hash.h"

#import <SenTestingKit/SenTestingKit.h>

@interface NSDictionary_HashTest : SenTestCase
@end

@implementation NSDictionary_HashTest

- (void)testHash
{
    NSDictionary *dict = [NSDictionary dictionaryWithObjectsAndKeys:
                          @"val1", @"key1", @"val2", @"key2", nil];
    NSUInteger result = 1;
    result = 31 * result + ([@"key1" hash] ^ [@"val1" hash]);
    result = 31 * result + ([@"key2" hash] ^ [@"val2" hash]);
    STAssertEquals([dict hash], result, nil);
}

@end

This test fails with "'2' should be equal to '2949297985'".

Now, if I rename the method from hash to hashy (for example) in the category header and implementation files, then [dict hashy] returns the correct value. Is it not possible to override a "built-in" method in a category? Am I doing something else wrong?

Cody, you definitely can override built in methods with categories. — xyzzycoder, Feb 04 '13 at 22:31
It used to be the case, and I am uncertain of the current situation, that if you had two categories with the same method name implemented, and both categories were part of a single class, the link order determined which method would actually be invoked by the runtime. A lot has changed in Objective-C over the last five years, so this behavior may be different now. — xyzzycoder, Feb 04 '13 at 23:05

Chuck · Accepted Answer · 2013-02-04T23:11:49.693

NSDictionary is a class cluster — when you send messages to an NSDictionary, what you interact with is never an actual instance of NSDictionary, but an instance of a private subclass. So when you override the hash method in your category, it is indeed overriding that method in NSDictionary, but the concrete subclass has its own hash method, so it overrides yours.

If you really want to do this, I think you'll want to check for the existence of the classes NSDictionaryI and NSDictionaryM and dynamically override their hash methods. But this is messing around in internal implementation details, and I would not recommend doing this unless you're somehow in really dire straits. If you profile and find NSDictionary's hash method is a problem, I would try creating a class that wraps an NSDictionary but provides its own custom hash method before mucking around with the private implementation classes — the implementation classes can change (and have before) without warning, so any design that relies on them is brittle.

Override hash value of NSArray

1 Answers1