Finding object using NSDictionary valueForKey vs. iterating through NSArray

Question

I'm working on a simple iOS caching system for some images. I need to keep track of the UIImage itself and its identifier. Now, I'm trying to figure out which is a faster/more efficient way to access the correct cached image.

Option 1:

for (CachedImage* image in [cachedImageArray]
{
  if ([[image identifier] isEqualToString:@"id_12345"]
  { 
    // use that image
  }
}

Option 2:

UIImage* imageToRetrieve = [cachedImagesDictionary objectForKey:@"id_12345"

Is there any benefit from using one method or the other? And if so, is it non-negligible? Thanks.

Answer 1

Dictionaries will most likely be faster, since they'll use some hashing algorithm to make the retrieval efficient (usually O(1) instead of O(n)). It will be non-negligible if the number of elements in your cache is large.

from CFDictionary.h

Computational Complexity
The access time for a value in the dictionary is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Insertion or deletion operations will typically be constant time as well, but are O(N*lg N) in the worst case in some implementations. Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.

Answer 2

Is there any benefit from using one method or the other?

Yes.

UIImage *imageToRetrieve = [cachedImagesDictionary objectForKey:@"id_12345"];

is much more readable.

(Oh, you meant performance? Don't worry about that. Premature optimization is the root of almost all evil.)