4. 再谈数组、集合、字典与 hash、isEqual 方法的关联

作者: halohily

我们或多或少了解,Objective-C 中的 NSArrayNSSetNSDictionaryNSObject 及其子类对象的 hashisEqual 方法有许多联系,这篇小集讲一下其中的一些细节。

NSArray 允许添加重复元素,添加元素时不查重,所以不调用上述两个方法。在移除元素时,会对当前数组内的元素进行遍历,每个元素的 isEqual 方法都会被调用(使用 remove 方法传入的元素作为参数),所有返回真值的元素都被移除。在字典中,不涉及 hash 方法。

NSSet 不允许添加重复元素,所以添加新元素时,该元素的 hash 方法会被调用。若集合中不存在与此元素 hash 值相同的元素,则它直接被加入集合,不调用 isEqual 方法;若存在,则调用集合内的对应元素的 isEqual 方法,返回真值则判等,不加入,处理结束。若返回 false,则判定集合内不存在该元素,将其加入。

从集合中移除元素时,首先调用它的 hash 方法。若集合中存在与其 hash 值相等的元素,则调用该元素的 isEqual 方法,若真值则判等,进行移除;若不存在,则会依次调用集合中每个元素的 isEqual 方法,只要找到一个返回真值的元素,就进行移除,并结束整个过程。(所以这样会有其他满足 isEqual 方法但却被漏掉未被移除的元素)。调用 contains 方法时,过程类似。

因此,若某自定义对象会被加入到集合或作为字典的 key 时,需要同时重写 isEqual 方法和 hash 方法。这样,若集合中某元素存在,则调用它的 containsremove 方法时,可以在 O(1) 完成查询。否则,查询它的时间复杂度提升为 O(n)

值得注意的是,NSDictionary 的键和值都是对象类型即可。但是被设为键的对象需要遵守 NSCopying 协议。

Last updated