Can't Retrieve Items from NSMutableDictionary Subclass

Question

I'm trying to create an ordered dictionary as a subclass of NSMutableDictionary. I used this article as a guide, but I tried doing my own implementation by reading the documentation of NSDictionary and NSMutableDictionary, which led to me doing it a little differently from the article. Namely, the argument for key to setObject:forKey: is supposed to be an id<NSCopying> (according to the documentation), which it isn't in the article.

The problem is when I set some value in setObject:forKey:, I can't retrieve it reliably - it will sometimes find the object for that key and sometimes not. I'm not using blocks or threads or GCD anywhere in my app so I don't understand how it could possibly behave randomly.

Here's my code:

// BBOrderedDictionary.h
@interface BBOrderedDictionary : NSMutableDictionary

@end

// BBOrderedDictionary.m
@interface BBOrderedDictionary ()

@property (nonatomic, strong) NSMutableArray* array;
@property (nonatomic, strong) NSMutableDictionary* dictionary;

@end

@implementation BBOrderedDictionary

-(instancetype)init
{
    return [self initWithCapacity:0];
}

-(instancetype)initWithCapacity:(NSUInteger)numItems
{
    self = [super init];
    if (self) {
        self.array = [NSMutableArray array];
        self.dictionary = [NSMutableDictionary dictionary];
    }

    return self;
}

# pragma mark - Primitive Methods

// NSMutableDictionary Primitive Methods

-(void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
    if (![self.dictionary objectForKey:aKey]) {
        [self.array addObject:aKey];
    }
    [self.dictionary setObject:anObject forKey:aKey];
}

-(void)removeObjectForKey:(id)aKey
{
    [self.dictionary removeObjectForKey:aKey];
    [self.array removeObject:aKey];
}

// NSDictionary Primitive Methods

-(NSUInteger)count
{
    return [self.dictionary count];
}

-(id)objectForKey:(id)aKey
{
    return [self.dictionary objectForKey:aKey];
}

-(NSEnumerator *)keyEnumerator
{
    return [self.array objectEnumerator];
}

#pragma mark - Other

-(NSArray *)allKeys
{
    return self.array;
}

@end

I should mention that my keys are a custom object as well, which conforms to NSCopying and implements isEqual:. It works just fine as a key in NSMutableDictionary.

When I set a breakpoint in objectForKey:, I can verify that the internal dictionary does indeed have everything I put into it, but (from putting logs in my key class's isEqual: method), it doesn't check all of its keys for equality with the key argument. Any ideas?

Answer 1

Whenever you implement a custom class and you implement the isEqual: method, you must also implement the hash method. See the docs for NSObject for details.

If these two methods do not properly work together then using the object in any sort of dictionary or set (basically any sort of hash map), then things won't work properly.

Note that two objects that return YES for isEqual: must return the same value for hash (which is not the default). However, two objects that are not equal (based on isEqual:) may or may not have the same hash value.

In theory you could simply return 1 for the hash of every object and things would work but it would make dictionaries and sets of these objects work very inefficiently. So make some attempt for unequal objects return different hash values.

Answer 2

NSDictionary is not a single class, but a class cluster. NSDictionary is the public interface to a family of different private classes that implement the functionality of the public interface. If you want to subclass a class cluster you have to implement all the primitive methods that support the public interface. See the Xcode docs on NSDictionary under "subclassing notes". That will tell you what you need to do, although I recommend against it.

Class clusters often do a lot of specialized optimization under the hood that would be difficult to imitate. It's usually better to create a custom object that manages an NSDictionary internally and presents some of the same methods as the dictionary class (a "has-a" relationship rather than an "is-a" relationship. Sometimes you can create a category to add features to one of these classes, although you can't override methods of the base class in a category.