cocoa - 哪种检查 NSDictionary 是否包含特定键的方法更快？

Question

我可以通过两种方式测试 NSDictionary 中是否存在键：

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

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

哪种方法更快，为什么？

Answer 1

一般来说，哈希查找应该比遍历所有字典键、从它们创建一个数组（内存分配相对昂贵）然后搜索数组（甚至不能是二进制搜索，因为数组没有排序）更快.

不过，为了科学起见，我制作了两个可执行文件，它们只执行每种样式 100 万次，并对它们进行计时。

使用 allKeys：

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

使用 objectForKey：

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

显然，各种因素都会影响这一点——字典的大小、缓存 allKeys 返回值等。不过，我不希望出现数组搜索比字典查找更快的情况。

Answer 2

我看不出请求 allKeys 数组可能会更快，否则 NSDictionary 至少会在内部执行等效操作。

编辑：我想你可以构建一个allKeys方法更快的案例 - 例如，通过在你的密钥方法中花费很长时间hash，而不是在你的isEqual:方法中。你也可以在一个疯狂的实现NSDictionary中交换它们（因为NSDictionary是抽象的。）

Answer 3

在考虑这样的性能问题时，请记住，Foundation 数据类会根据您在其中存储的对象数量来交换其底层数据结构。例如，我认为一个小的 NSArray 实际上使用哈希表进行存储，直到它达到一定的大小。