47

注意：以下 SO 问题是相关的，但它们和链接的资源似乎都没有完全回答我的问题，特别是与实现对象集合的相等测试有关。

背景

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

语境

我开发了 CHDataStructures.framework，这是一个 Objective-C 数据结构的开源库。我已经实现了许多集合，目前正在改进和增强它们的功能。我想添加的功能之一是能够将集合与另一个集合进行比较。

这些比较应该考虑两个集合中存在的对象（包括排序，如果适用），而不是只比较内存地址。这种方式在Cocoa中有相当的先例，一般采用单独的方式，包括以下几种：

我想让我的自定义集合对相等性测试具有鲁棒性，因此它们可以安全地（并且可预测地）添加到其他集合中，并允许其他集合（如 NSSet）确定两个集合是否相等/等价/重复。

问题

一个-isEqualTo...:方法本身就可以很好地工作，但是如果参数与接收者属于同一类（或者可能是子类），或者其他情况下，定义这些方法的类通常也会覆盖-isEqual:以调用。这意味着该类还必须定义为，它将为具有相同内容的不同实例返回相同的值。[self isEqualTo...:][super isEqual:]-hash

此外，Apple 的文档-hash规定如下：（强调我的）

“如果将可变对象添加到使用哈希值确定对象在集合中的位置的集合中，则该对象的哈希方法返回的值在对象在集合中时不得更改。因此，无论是哈希方法不得依赖任何对象的内部状态信息，或者您必须确保对象在集合中时对象的内部状态信息不会改变。因此，例如，可以将可变字典放入哈希表中，但您必须当它在那里时不要更改它。（请注意，很难知道给定对象是否在集合中。）“

编辑： 我完全理解为什么这是必要的，并且完全同意这个推理——我在这里提到它是为了提供额外的背景，并为了简洁而避开了为什么会这样的话题。

我所有的集合都是可变的，并且哈希必须至少考虑一些内容，所以这里唯一的选择是认为改变存储在另一个集合中的集合是一个编程错误。（我的收藏都采用了NSCopying，所以像 NSDictionary 这样的收藏可以成功地制作副本作为密钥等）

-isEqual:实现and对我来说是有意义的-hash，因为（例如）我的一个类的间接用户可能不知道-isEqualTo...:要调用的具体方法，甚至不关心两个对象是否是同一个类的实例。他们应该能够调用-isEqual:或调用-hash任何类型的变量id并获得预期的结果。

与-isEqual:（可以访问被比较的两个实例）不同，-hash必须“盲目地”返回结果，只能访问特定实例中的数据。由于它无法知道哈希的用途，因此对于所有应该被视为相等/相同的可能实例，结果必须一致，并且必须始终与-isEqual:. （编辑：这已经被下面的答案揭穿了，它确实让生活更轻松。）此外，编写好的散列函数并非易事——保证唯一性是一个挑战，尤其是当你只有一个 NSUInteger（32/64 位）时在其中代表它。

问题

  1. 为集合实施相等比较 时是否有最佳实践？-hash
  2. 在 Objective-C 和 Cocoa 风格的集合中是否有任何特殊需要计划？
  3. -hash是否有任何具有合理置信度的单元测试的好方法？
  4. 关于实施-hash以同意-isEqual:包含任意类型元素的集合的任何建议？我应该知道哪些陷阱？（编辑：不像我最初想的那样有问题——正如@kperryua指出的那样，“相等的-hash值并不意味着-isEqual:”。）

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

4

3 回答 3

18

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

我的建议是不要太担心集合的散列。正如您所说，-isEqual:意味着相等-hash的值。另一方面，相等的-hash值并不意味着-isEqual:。这个事实给了你很大的余地来创建一个简单的哈希。

但是，如果您真的担心碰撞（并且您在实际情况的具体测量中证明了这是值得担心的事情），您仍然可以在某种程度上遵循 U62 的建议。例如，您可以获取集合中第一个和/或最后一个元素的哈希值，并将其与集合的 the 相结合-count。这足以提供一个像样的哈希。

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

至于第 1 点：实施-isEqual:非常简单。您枚举内容，并检查每个元素上的 isEqual:。

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

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

于 2009-07-11T06:43:57.537 回答
4

如果两个集合包含相同的元素，则它们应该被认为是相等的，并且如果集合是有序的，则元素的顺序相同。

关于集合的散列，以某种方式组合元素的散列应该足够了（异或或模相加）。请注意，虽然规则规定根据 IsEqual 相等的两个对象需要返回相同的散列，但相反的情况并不成立：尽管散列的唯一性是可取的，但对于解决方案的正确性来说，这不是必需的。因此，有序集合不需要考虑元素的顺序。

顺便说一句，Apple 文档的摘录是一个必要的限制。一个对象在突变下不能保持相同的哈希值，同时还要确保具有相同值的对象具有相同的哈希值。这适用于最简单的对象和集合。当然，当对象在使用散列来组织其元素的容器内时，对象的散列变化通常很重要。所有这一切的结果是可变集合在放置在另一个容器中时不应该发生变异，但是任何具有真正散列函数的对象也不应该发生变异。

于 2009-07-11T00:26:56.893 回答
3

我已经对 NSArray 和 NSMutableArray 默认哈希实现进行了一些调查，并且（除非我误解了某些东西）它看起来像 Apple 不遵循他们自己的规则：

如果将可变对象添加到使用哈希值确定对象在集合中的位置的集合中，则当对象在集合中时，对象的哈希方法返回的值不得更改。因此，散列方法不能依赖任何对象的内部状态信息，或者您必须确保对象在集合中时对象的内部状态信息不会改变。因此，例如，可以将可变字典放入哈希表中，但您不能在其中更改它。（请注意，很难知道给定对象是否在集合中。）

这是我的测试代码

NSMutableArray* myMutableArray = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
NSMutableArray* containerForMutableArray = [NSMutableArray arrayWithObject:myMutableArray];

NSUInteger hashBeforeMutation = [[containerForMutableArray objectAtIndex:0] hash];
[[containerForMutableArray objectAtIndex:0] removeObjectAtIndex:1];
NSUInteger hashAfterMutation = [[containerForMutableArray objectAtIndex:0] hash];

NSLog(@"Hash Before: %d", hashBeforeMutation);
NSLog(@"Hash After : %d", hashAfterMutation);

输出是：

Hash Before: 3
Hash After : 2

所以它看起来像 NSArray 和 NSMutableArray 上的 Hash 方法的默认实现是数组的计数，它不关心它是否在集合中。

于 2012-07-10T09:53:03.743 回答