对于大型NSDictionary,objectForKey是否缓慢？

Question

1. 假设我们有非常大的NSDictionary,当我们想要调用objectForKey方法时,它会在核心中进行大量操作来获取值吗？或者它会直接指向内存中的值吗？
2. 它在核心中如何运作？

Answer 1

Core Foundation编程主题的CFDictionary部分(如果您想了解更多信息,请查看):

字典 - CFDictionary类型的对象 - 是基于散列的集合,其访问其值的键是任意的,程序定义的数据片段(或指向数据的指针).虽然键通常是一个字符串(或者,在Core Foundation中,一个CFString对象),但它可以是任何可以适合指针大小的东西 - 整数,对Core Foundation对象的引用,甚至是指向数据的指针结构(不太可能).

这就是维基百科对哈希表的看法:

理想情况下,散列函数应将每个可能的键映射到唯一的插槽索引,但这种理想在实践中很难实现(除非散列键是固定的;即新条目在创建后永远不会添加到表中).相反,大多数哈希表设计都假设哈希冲突 - 映射到相同哈希值的不同密钥 - 将发生并且必须以某种方式容纳.在尺寸合适的哈希表中,每次查找的平均成本(指令数)与表中存储的元素数无关.许多哈希表设计还允许以每个操作的恒定平均(实际上,摊销)成本任意插入和删除键值对.

因此,性能取决于散列的质量.如果它是好的,那么访问元素应该是O(1)操作(即不依赖于元素的数量).

编辑:

事实上,在进一步阅读了Core Foundation的Collections Programming Topics后,apple会回答你的问题:

对于任何实现,CFDictionary对象中的值的访问时间保证最差为O(log N),但通常为O(1)(常量时间).插入或删除操作通常也处于恒定时间,但在最坏的情况下是O(N*log N).通过密钥访问值比直接访问它更快.字典往往比具有相同数值的数组使用更多的内存.