实现-hash-isEqual： -isEqualTo …：用于Objective-C集合

概述注意：以下SO问题是相关的，但它们或链接的资源都不能完全回答我的问题，特别是在实现对象集合的等式测试方面。 > Best practices for overriding -isEqual: and -hash > Techniques for implementing -hash on mutable Cocoa objects 背景 NSObject提供了-hash(返回实例的地址，例如(NS 注意：以下SO问题是相关的，但它们或链接的资源都不能完全回答我的问题，特别是在实现对象集合的等式测试方面。

> Best practices for overriding -isEqual: and -hash
> Techniques for implementing -hash on mutable Cocoa objects

背景

NSObject提供了-hash(返回实例的地址，例如(NSUInteger)self)和-isEqual:(除非接收器和参数的地址相同，否则返回NO)的默认实现。这些方法被设计为在必要时被覆盖，但文档清楚地表明您应该提供两者，或两者都不提供。此外，如果-isEqual：对两个对象返回YES，那么这些对象的-hash结果必须相同。如果不是，那么应该是相同的对象(例如两个字符串实例-compare：returns NSOrderedSame)会被添加到Cocoa集合或直接比较。

上下文

我开发了CHDataStructures.framework，一个Objective-C数据结构的开源库。我实现了一些集合，并且目前正在改进和增强其功能。我想添加的一个功能是能够比较集合与另一个相等。

不是仅比较存储器地址，这些比较应该考虑两个集合中存在的对象(包括排序，如果适用)。这种方法在Cocoa中有相当先例，通常使用单独的方法，包括以下内容：

> -[NSArray isEqualToArray:]
> -[NSDate isEqualToDate:]
> -[NSDictionary isEqualToDictionary:]
> -[NSNumber isEqualToNumber:]
> -[NSSet isEqualToSet:]
> -[NSString isEqualToString:]
> -[NSValue isEqualToValue:]

我想让我的自定义集合对平等测试是稳健的，所以他们可以安全地(可预见地)添加到其他集合，并允许其他(如NSSet)确定两个集合是否相等/等价/重复。

问题

一个-isEqualTo …：方法本身很好，但是定义这些方法的类通常也重写-isEqual：如果参数是相同的类(或者可能是子类)，则调用[self isEqualTo …：]：接收者，否则为[super isEqual：]。这意味着类还必须定义-hash，以便它对具有相同内容的不同实例返回相同的值。

此外，苹果的文档–hash规定如下：(强调我)

“If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection,the value returned by the hash method of the object must not change while the object is in the collection. Therefore,either the hash method must not rely on any of the object’s internal state information or you must make sure the object’s internal state information does not change while the object is in the collection. Thus,for example,a mutable dictionary can be put in a hash table but you must not change it while it is in there. (Note that it can be difficult to kNow whether or not a given object is in a collection.)”

编辑：我绝对明白为什么这是必要的，完全同意推理 – 我提到它在这里提供额外的上下文，并提出了为什么为了简洁的情况的主题。

我的所有集合是可变的，并且哈希将必须考虑至少一些内容，所以这里唯一的选择是考虑一个编程错误，以突变另一个集合中存储的集合。 (我的集合都采用NSCopying，所以像NSDictionary的集合可以成功地做一个副本用作一个键等)

实现-isEqual：和-hash是有意义的，因为(例如)我的一个类的间接用户可能不知道具体的-isEqualTo …：方法来调用，甚至关心两个对象是否是实例的同类。他们应该能够调用-isEqual：或-hash任何类型ID的变量，并得到预期的结果。

与-isEqual：(可以访问两个实例进行比较)不同，-hash必须返回一个结果“blindly”，只访问特定实例中的数据。由于它不能知道使用什么哈希，所以对于应该被认为相等/相同的所有可能的实例，结果必须是一致的，并且必须总是与-isEqual：一致。此外，编写良好的哈希函数是非平凡的 – 保证唯一性是一个挑战，尤其是当你只有一个NSUInteger(32/64位)时，在其中代表它。

问题

>在实现平等比较时是否有最佳实践 – 集合的哈希？
>在Objective-C和Cocoa-esque系列中有什么特殊的规划？
>有没有任何好的方法进行单元测试 – 具有合理的置信度？
>有关实现-hash以同意-isEqual：对包含任意类型的元素的集合的任何建议？我应该知道什么陷阱？ (编辑：不像我第一次想到的那样有问题 – 正如@kperryua指出的，“等于-hash值不意味着-isEqual：”。)

编辑：我应该澄清，我不困惑如何实现-isEqual：或-isEqualTo …：对集合，这很直接。我认为我的混乱主要来自(错误地)认为 – 哈希必须返回不同的值如果-isEqual：返回NO。在过去完成加密之后，我认为不同值的哈希必须不同。然而，下面的答案让我意识到，一个“好的”哈希函数真的关于最小化桶碰撞和链接使用-hash的集合。虽然独特的哈希是优选的，但它们不是严格的要求。

解决方法 我想试图想出一些一般有用的哈希函数，将生成集合的唯一哈希值是一个徒劳的练习。 U62的组合所有内容的哈希的建议将不能很好地缩放，因为它使得散列函数O(n)。哈希函数应该真的是O(1)以确保良好的性能，否则哈希的目的被打败。 (考虑普通的Cocoa构造的pLists，它是包含数组和其他字典的字典，可能是恶意的)如果集合的哈希函数是O()，则尝试获取大型pList的顶级字典的哈希将是非常缓慢的n)。

我的建议是不要担心大量的集合的哈希。正如你所说，-isEqual：暗示等于-hash值。另一方面，等于-hash值并不意味着-sequal：。这个事实给你很多余地创建一个简单的哈希。

如果你真的担心碰撞，虽然(和你有实际测量的现实世界的情况下的证据，确认它是一个担心)，你仍然可以在一定程度上遵循U62的建议。例如，您可以获取集合中的第一个和/或最后一个元素的哈希值，并将它与例如集合的-count结合使用。这足以提供一个体面的哈希。

我希望至少回答一个你的问题。

至于第1：实施-isEqual：是相当干燥。你枚举的内容，并检查isEqual：每个元素。

有一件事要小心，可能会影响你决定为你的集合的-hash函数做什么。集合的客户端还必须了解管理-isEqual：和-hash的规则。如果您使用集合的-hash中的内容’-hash，如果内容’isEqual：和-hash不同意，您的集合将会中断。这是客户的错，当然，但这是另一个反对根据你的收集的内容。

第2号是模糊的。不知道你有什么想法。

总结

以上是内存溢出为你收集整理的实现-hash/-isEqual：/ -isEqualTo …：用于Objective-C集合全部内容，希望文章能够帮你解决实现-hash/-isEqual：/ -isEqualTo …：用于Objective-C集合所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。