Является ли objectForKey медленным для большого NSDictionary?

  • Предположим, что у нас очень большой NSDictionary, когда мы хотим вызвать метод objectForKey, будет ли он делать много операций в ядре, чтобы получить значение? Или он будет указывать на значение в памяти напрямую?
  • Как это работает в ядре?

Ответы

Ответ 1

В разделе CFDictionary раздела Темы программирования для Core Foundation (который вы должны изучить, если хотите узнать больше):

Словарь - объект типа CFDictionary - это хеширование чьи ключи для доступа к своим значениям произвольны, программные части данных (или указатели на данные). Хотя ключ обычно является строкой (или в Core Foundation, объекте CFString), это может быть любым, что может вписываться в размер указателя - целое число, ссылка на объект Core Foundation, даже указатель на данные (вряд ли это возможно).

Это то, что википедия должна сказать о хэш-таблицах:

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

Таким образом, производительность зависит от качества хэша. Если это хорошо, то доступ к элементам должен быть операцией O (1) (то есть не зависит от количества элементов).

ИЗМЕНИТЬ:

Фактически, после того, как я прочитал далее разделы "Вопросы программирования коллекций для Core Foundation", apple дает ответ на ваш вопрос:

Время доступа для значения в объекте CFDictionary гарантируется быть в худшем случае O (log N) для любой реализации, но часто O (1) (постоянное время). Операции вставки или удаления обычно находятся в постоянное время, но O (N * log N) в худших случаях. это быстрее получить доступ к значениям через ключ, чем напрямую обращаться к ним. Словари, как правило, используют значительно больше памяти, чем массив с такое же количество значений.

Ответ 2

NSDictionary - это, по существу, структура таблицы Hash, поэтому Big-O для поиска - O (1). Однако, чтобы избежать перераспределения (и для достижения сложности O (1)), вы должны использовать dictionaryWithCapacity: для создания нового Словаря с соответствующим размером в зависимости от размера вашего набора данных.