NSArray 与 NSDictionary 查找

Question

检查对象是否已存在于列表中更快且成本更低。通过使用 NSArray 包含对象还是通过检查 NSDictionary 的键是否已经存在？

NSArray containsObject 选择器也遍历整个数组元素吗？另外如何检查字典中是否已经存在一个键？这是否需要遍历所有键。

最后，检查对象是否已存在于大型对象列表（同一类）中的最佳和最快方法是什么。

提前致谢

Answer 1

根据 Collection Classes 的文档，NSDictionary 基于 HashTables。这意味着如果你在字典中搜索一个键，所需的时间比遍历一个数组少很多。

因此，搜索密钥应该是 o(1+numberofcollisions)。其中遍历数组是 o(n)。您可以对数组进行快速排序，然后对其进行二分搜索，这将大大降低成本。然而，对于您来说，NSDictionary（哈希表）对于搜索来说非常便宜。

来自苹果文档

在内部，字典使用哈希表来组织其存储并提供对给定相应键值的快速访问。但是，为字典定义的方法使您免于使用哈希表、哈希函数或键的哈希值的复杂性。这些方法直接采用密钥，而不是散列形式。