В разделе CFDictionary Темы программирования коллекций для Core Foundation (с которыми вам следует ознакомиться, если вы хотите узнать больше) говорится:
Словарь - объект типа CFDictionary - основан на хешировании
коллекция, ключи которой для доступа к ее значениям являются произвольными,
программно определенные части данных (или указатели на данные). Хотя ключ
обычно это строка (или, в Core Foundation, объект CFString), это
может быть любым, что может вписаться в размер указателя - целое число,
ссылка на базовый объект Foundation, даже указатель на данные
структура (маловероятно, что это может быть).
Вот что говорит Википедия о хеш-таблицах:
В идеале хеш-функция должна отображать каждую возможную клавишу на уникальный
индекс слота, но этот идеал редко достижим на практике (если
ключи хеша исправлены; то есть новые записи никогда не добавляются в таблицу
после того как он создан). Вместо этого большинство конструкций хеш-таблиц предполагают, что
хеш-коллизии - разные ключи, которые отображаются на одно и то же хеш-значение -
происходят и должны быть приспособлены каким-либо образом. В размерном хеше
Таблица, средняя стоимость (количество инструкций) для каждого поиска составляет
не зависит от количества элементов, хранящихся в таблице. Много хеш
дизайн таблицы также позволяет произвольные вставки и удаления
пары ключ-значение при постоянной средней (действительно, амортизированной) стоимости за
работа.
Поэтому производительность зависит от качества хэша. Если это хорошо, то доступ к элементам должен быть операцией O (1) (т.е. не зависит от количества элементов).
РЕДАКТИРОВАТЬ:
На самом деле, после прочтения разделов по программированию коллекций для Core Foundation, Apple дает ответ на ваш вопрос:
Время доступа к значению в объекте CFDictionary гарантировано
быть в худшем случае O (log N) для любой реализации, но часто O (1)
(постоянное время). Операции вставки или удаления обычно
постоянное время, но в худшем случае O (N * log N). это
быстрее получить доступ к значениям с помощью ключа, чем непосредственно к ним.
Словари, как правило, используют значительно больше памяти, чем массив с
одинаковое количество значений.