iphone - NSArray 与 NSDictionary 查找

Question

检查一个对象是否已经存在于列表中，哪个更快更便宜。通过使用 NSArray 包含对象或通过检查 NSDictionary 的键是否已经存在？

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

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

提前致谢

Answer 1

根据集合类的文档，NSDictionary 是基于哈希表的。这意味着如果您在字典中搜索键，所需时间比遍历数组少得多。

所以，搜索一个键应该是o(1+numberofcollisions)。遍历数组的时间复杂度为 o(n)。您可以快速排序数组然后对其进行二进制搜索，这将使成本大大降低。然而，为了您的利益，NSDictionary(哈希表)的搜索成本非常低。

来自苹果 docs

Internally, a dictionary uses a hash table to organize its storage and to provide rapid access to a value given the corresponding key. However, the methods defined for dictionaries insulate you from the complexities of working with hash tables, hashing functions, or the hashed value of keys. The methods take keys directly, not in their hashed form.