Вычислительная сложность CFDictionary

Question

Я смотрел в Core Foundation и CFDictionary, и в документации Apple я нашел это,

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

К моему удивлению, в источнике CFDictionary я нашел это,

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

Почему такая разница..? или я смотрю не в том месте?

Редактировать: в Apple OpenSource Browser, почему так много папок, которые похожи на разные версии Core Foundation, не так ли?.. Что из этого является последним / актуальным?

Answer 1

"В некоторых реализациях". Поскольку у вас есть источник, вы можете легко проверить, какой наихудший случай для вашей реализации. В худшем случае предположим, что каждый объект в словаре возвращает значение хеш-функции 0:-)

КСТАТИ. В худшем случае произойдет, когда хэш-таблица заполнится и будет полностью восстановлена. Вот почему вы используете амортизированное время, а не худшее, если только для вас не важно худшее время для одной вставки.