NSSet是否使用哈希来定义唯一性？

Question

我一直在假设NSSet使用hash查找潜在的匹配,然后在每个上面调用isEqual来检查真正的冲突,但我意识到我找不到任何证据支持这一点.

我提出的原因是NSSet中存在"member:"方法.为什么成员的文档:尽量指定isEqual:用于在NSSet中没有别的时候找到你的对象？containsObject:只使用哈希或其他什么？

谁能证实这种行为？理想情况下,参考文档呢？

Answer 1

我建议阅读Collections Programming Topics,特别是'Sets:Unordered Collections of Objects'部分.在那里,您将找到以下信息:

此性能信息假定为对象定义的哈希方法有足够的实现.使用错误的哈希函数,访问和编辑需要线性时间.

和

集合中的对象必须响应NSObject协议方法hash和isEqual :(有关更多信息,请参阅NSObject).如果可变对象存储在一个集合中,则对象的哈希方法不应该依赖于可变对象的内部状态,或者当它们在集合中时不应该修改可变对象.例如,可变字典可以放在一个集合中,但是当它在那里时你不能改变它.(注意,可能很难知道给定对象是否在集合中).

所以,是的,hash和isEqual是按照你的假设使用的.

Answer 2

我想介入,并提供有关的NSSet的使用进一步的信息hash和isEqual:,因为我最近遇到了莫名其妙的错误,发现他们是由于我俯瞰hash.

在集合中存储自定义对象时,NSSet使用hash方法返回的值将不同容器中的对象分组,在这些容器中使用各自的isEqual:方法将它们相互比较.因此,基本上,hash在插入,构建,测试成员资格等时,将始终在对象上调用,如果此对象落入有其他对象的bin中,isEqual则将使用其方法将其与它们区分开来.

这就是为什么对于被认为相等的对象hash必须始终相同,并且尽可能地产生将均匀地传播对象的屈服值.后一种属性确保了垃圾箱尽可能小,最大限度地减少了呼叫isEqual:.