NSArray vs NSDictionary look up

Question

Which is quicker and less expensive for checking if an object already exists within a list. By using the NSArray contains object or by checking if a key already exists for an NSDictionary?

Also does the NSArray containObject selecter iterate through the whole array elements? Also what about checking if a key already exists within a dictionary? Does that require iterating through all the keys.

Finally, what is the best and quickest way to check if an object already exists within a large list of objects (of the same class).

Thanks in advance

Answer 1

How many values are you talking about? The difference in speed may be irrelevant, thus making the choice be the one that makes the most sense in the code. In fact, that should probably be the first priority, unless and until you know that there is a speed problem.

Short version: Use NSDictionary unless you have a specific need not to.

Answer 2

According to the document of Collection Classes the NSDictionary is based on HashTables. Which means if you are searching for a key in a dictionary, the time required is mush less than iterating through an array.

So, searching for a key should be o(1+numberofcollisions). where iterating through an array is o(n). You can quick sort array then binary search it which will make the cost a lot less. However for your buck, NSDictionary (hash table) are very cheap for searching.

From Apple docs

Internally, a dictionary uses a hash table to organize its storage and to provide rapid access to a value given the corresponding key. However, the methods defined for dictionaries insulate you from the complexities of working with hash tables, hashing functions, or the hashed value of keys. The methods take keys directly, not in their hashed form.

Answer 3

I would say that the fastest way would be to sort your array when you insert an object:

NSMutableArray *myArray;

[myArray addObject:someCustomObject];
[myArray sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    // custom compare code here
}];

While this takes performance out of inserting an object, it would greatly increase your lookup times.

To do a binary search on a NSArray:

BOOL binarySearchContains(NSArray *sortedArray, id object, NSComparator comparisonBlock)
{
    // simple recursive helper function
    __block BOOL (^_binaryRecurse)(NSArray *, id, int lo, int hi) = ^BOOL(NSArray *array, id object, int lo, int hi)
    {
        int middleIndex = ((hi - lo) / 2) + lo;

        if (hi == lo || middleIndex < 0 || middleIndex >= [array count])
            return NO;

        int compareResult = (comparisonBlock(object, [array objectAtIndex:middleIndex]));

        if (compareResult < 0)
            return _binaryRecurse(array, object, lo, middleIndex - 1);
        if (compareResult > 0)
            return _binaryRecurse(array, object, middleIndex + 1, hi);

        return YES;
    };

    return _binaryRecurse(sortedArray, object, 0, [sortedArray count]);
}

In my tests, the bsearch is approximately 15 times faster than -containsObject:.