NSSet with dictionaries: Get object by Value of Key

Question

I have the following constellation using an NSSet:

NSSet {
    NSDictionary {
        "Unique-Identifier-Key": Unique Value
        "Key2": ValueABC
        "Key3": ValueDEF
    }

    NSDictionary {
        "Unique-Identifier-Key": Unique Value
        "Key2": ValueFGH
        "Key3": ValueJKL
    }

    NSDictionary {
        "Unique-Identifier-Key": Unique Value
        "Key2": ValueRST
        "Key3": ValueXYZ
    }
}

I'm searching for a way to get one dictionary out of the NSSet by its Unique Value. There are quite a lot NSDictionaries in that NSSet and therefore I'm searching for the way with the best performance.

How about using (NSSet *)objectsPassingTest:(BOOL (^)(id obj, BOOL *stop))predicate in the following way?

NSString *idSearched = ...;
NSSet *results = [MySet objectsPassingTest:^(id obj,BOOL *stop){
    if ([obj valueForKey:@"Unique-Identifier-Key"] == idSearched) return YES;
    else return NO;
}];

Is this the most performant solution? I used NSSet as I read that NSSets have a better performance than NSArrays for finding objects. And I don't need an ordered sequence of the objects.

Answer 1

I think the actual layout you want is:

NSDictionary {
    Unique Value: NSDictionary {
        "Key2": ValueABC
        "Key3": ValueDEF
    }

    Unique Value: NSDictionary {
        "Key2": ValueFGH
        "Key3": ValueJKL
    }

    Unique Value: NSDictionary {
        "Key2": ValueRST
        "Key3": ValueXYZ
    }
}

Basically, rather than storing the unique key/value pair inside the dictionary, have a new dictionary where the unique value is the key to the other data. If your unique value is an NSString then you'll find you'll probably get close to O(1) time complexity.

You can convert your set to the above layout using the following code:

NSMutableDictionary *searchable = [NSMutableDictionary dictionary];
for (NSDictionary *dict in MySet)
    [searchable setObject:dict forKey:[dict objectForKey:@"Unique-Identifier-Key"]];

(although it would be better to load the data directly into the structure described above rather than converting it from a set). Then, whenever you want to find one of your dictionaries:

NSDictionary *dict = [searchable objectForKey:idSearched];

Answer 2

I don't think it helps you with performance when you use NSSet like that. NSSet has better performance than NSArray due to either hash algorithms or some sorting algorithms. If you use a predicate like that, I think the NSSet has to search over the whole collection to find the item you need.

I would suggest you create a new class MyObject, that contains your NSDictionary, and override the hash and isEqual

- (BOOL)isEqual:(id)object;
- (NSUInteger)hash;

In the hash, you return your unique value hash and that would improve your performance. But if you have very few objects that you need to search, you may just go with your simple predicate