objective-c - 实现 -hash/-isEqual :/-isEqualTo. ..:用于 Objective-C 集合

Question

注:以下 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:返回 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这样它将为具有相同内容的不同实例返回相同的值。
此外，Apple 的文档 -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 这样的收藏可以成功制作副本作为key等)
实现 -isEqual: 对我来说很有意义和 -hash ，因为(例如)我的一个类(class)的间接用户可能不知 Prop 体的 -isEqualTo...:方法调用，甚至关心两个对象是否是同一个类的实例。他们应该可以拨打 -isEqual:或 -hash任何类型的变量 id并得到预期的结果。
不像 -isEqual: (可以访问正在比较的两个实例)， -hash必须“盲目地”返回结果，只能访问特定实例中的数据。由于它无法知道散列用于什么，结果必须与 一致。全部 应该被视为相等/相同的可能实例，并且必须始终同意 -isEqual: . (编辑:这已经被下面的答案揭穿了，它确实让生活更轻松。)此外，编写好的哈希函数并非易事——保证唯一性是一个挑战，尤其是当你只有一个 NSUInteger(32/64 位)时在其中代表它。
问题

实现相等比较时是否有最佳实践-hash为了收藏？

在 Objective-C 和 Cocoa 风格的集合中是否有任何特殊之处需要规划？

单元测试有什么好的方法-hash有合理的信心？

关于实现的任何建议-hash同意 -isEqual:对于包含任意类型元素的集合？我应该知道哪些陷阱？ ( 编辑: 不像我最初想的那样有问题——正如@kperryua 指出的那样，“等于 -hash 值是 不是 暗示 -isEqual:5|6|79

编辑:我应该澄清一下，我对如何实现 -isEqual: 或 -isEqualTo...: 对于集合并不感到困惑，这很简单。我认为我的困惑主要源于(错误地)认为 -hash 必须返回不同的值，如果 -isEqual: 返回 NO。过去做过密码学，我认为不同值的散列必须不同。然而，下面的答案让我意识到一个“好的”散列函数实际上是关于最小化桶冲突和链接使用 -hash 的集合。 .虽然最好使用唯一的哈希值，但它们并不是严格的要求。

Answer 1

我认为尝试提出一些通常有用的散列函数来为集合生成唯一的散列值是徒劳的。 U62 建议将所有内容的散列组合起来并不能很好地扩展，因为它使散列函数为 O(n)。散列函数确实应该是 O(1) 以确保良好的性能，否则散列的目的就落空了。 (考虑 plist 的常见 Cocoa 构造，它们是包含数组和其他字典的字典，可能令人恶心。如果集合的散列函数是 O( n))

我的建议是不要太担心集合的哈希值。正如你所说，-isEqual:意味着相等 -hash值。另一方面，等于 -hash值做不是 暗示 -isEqual: .这一事实为您提供了很多创建简单哈希的余地。

如果你真的很担心碰撞(并且你有真实世界情况的具体测量证据，证实它是值得担心的事情)，你仍然可以在某种程度上遵循 U62 的建议。例如，您可以获取集合中第一个和/或最后一个元素的哈希值，并将其与 -count 相结合。的集合。这足以提供一个体面的哈希。

我希望这至少能回答您的一个问题。

至于第一:实现 -isEqual:非常干净和干燥。您枚举内容，并在每个元素上检查 isEqual: 。

有一件事情需要注意，这可能会影响您决定为您的收藏做什么-hash职能。您收藏的客户还必须了解管理规则 -isEqual:和 -hash .如果您使用内容'-hash在您收藏的 -hash ，如果内容'isEqual:，您的收藏将被破坏和 -hash不同意。当然，这是客户的错，但这是反对建立 -hash 的另一个论据。关闭集合的内容。

2 号有点含糊。不知道你有什么想法。