Какой метод проверки, чтобы узнать, содержит ли NSDictionary конкретный ключ быстрее?

Я могу проверить наличие ключа в NSDictionary двумя способами:

BOOL containsKey = [[dictionary allKeys] containsObject:foo];

BOOL containsKey = ([dictionary objectForKey:foo] != nil);

какой метод быстрее, и почему?

Ответ 1

Хэш-поиск должен быть быстрее в общем, чем переходить ко всем клавишам словаря, создавая из них массив (распределение памяти относительно дорого), а затем ищет массив (который даже не может быть бинарным поиском, так как массив не отсортировано).

Для науки, однако, я сделал два исполняемых файла, которые просто исполняли каждый стиль 1 миллион раз и приурочили их.

С allKeys:

real    0m4.185s
user    0m3.890s
sys     0m0.252s

С objectForKey:

real    0m0.396s
user    0m0.189s
sys     0m0.029s

Очевидно, на этот размер могут влиять различные факторы: размер словаря, кэширование возвращаемого значения allKeys и т.д. Я бы не ожидал, что там будет случай, когда поиск массива будет быстрее, чем поиск в словаре.

Ответ 2

Я не вижу, как запрос массива allKeys может быть быстрее, иначе NSDictionary по крайней мере сделает эквивалент внутри.

EDIT: Я полагаю, что вы могли бы построить случай, когда метод allKeys был бы быстрее - долгое время в ключевом ключе hash, но не в вашем методе isEqual:, например. И вы также можете поменять местами сумасшедшую реализацию для NSDictionary, в которой они также меняются местами (поскольку NSDictionary является абстрактным.)

Ответ 3

Рассматривая такие вопросы производительности, помните, что классы данных Foundation заменяют свои базовые структуры данных в зависимости от того, сколько объектов вы храните в них. Например, я думаю, что небольшой NSArray фактически использует хеш-таблицу для хранения, пока не достигнет определенного размера.