为Objective-C集合实现-hash / -isEqual:/ -isEqualTo …:

注意:下面的SO问题是相关的,但是他们和链接的资源似乎都不能完全回答我的问题,特别是在实现对象集合的平等testing方面。

  • 覆盖-isEqual和-hash的最佳实践
  • 在可变的cocoa对象上实现-hash的技巧

背景

NSObject提供了默认的实现-hash (它返回实例的地址,比如(NSUInteger)self )和-isEqual:除非接收者的地址和参数相同,否则返回NO 。 这些方法被devise为根据需要被覆盖,但是文档清楚地表明你应该提供或者不提供。 此外,如果-isEqual:对于两个对象返回YES ,则这些对象的-hash结果必须相同。 如果不是这样,那么当对象应该是相同的,比如两个string实例(其中的NSOrderedSame -compare: returns NSOrderedSame )被添加到Cocoa集合中,或者直接进行比较时,问题会随之而来。

上下文

我开发了CHDataStructures.framework ,一个Objective-C数据结构的开源库。 我已经实现了一些集合,并且正在改进和增强它们的function。 我想要添加的function之一是能够比较集合的平等与另一个。

这些比较应该考虑两个集合中存在的对象(包括sorting,如果适用),而不是只比较内存地址。 这种方法在cocoa中有相当的先例,并且通常使用一种单独的方法,包括以下方法:

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

我想使自定义集合对于相等性testing的健壮性,所以他们可以安全地(可预测地)将其添加到其他集合中,并允许其他集合(如NSSet)确定两个集合是否相等/等同/重复。

问题

一个-isEqualTo...:方法可以很好地工作,但是定义这些方法的类通常也会覆盖-isEqual:如果参数是相同的类(或者可能是子类),则调用[self isEqualTo...:]接收者,否则[super isEqual:] 。 这意味着该类还必须定义-hash ,以便为具有相同内容的不同实例返回相同的值。

另外,苹果的-hash文件规定如下:(强调我的)

“如果将可变对象添加到使用散列值确定对象在集合中的位置的集合中,则在对象位于集合中时,由对象的散列方法返回的值不得更改,因此无论是散列方法不能依赖任何对象的内部状态信息, 或者当对象位于集合中时,必须确保对象的内部状态信息不发生变化。因此,例如,可以将可变字典放在哈希表中,但必须而不是在它那里改变它(注意可能很难知道一个给定的对象是否在一个集合中)。“

编辑: 我当然明白为什么这是必要的,并完全同意推理 – 我在这里提到它提供了额外的背景,并且为了简洁起见跳过为什么是这样的话题。

我所有的集合都是可变的,哈希将不得不考虑至less一些内容,所以这里唯一的select是将其存储在另一个集合中的集合进行变异时,将其视为编程错误。 (我的集合都采用NSCopying ,所以像NSDictionary集合可以成功地作为一个副本作为一个键等)

因为(例如)我的一个类的间接用户可能不知道要调用的特定的-isEqualTo...:方法,或者甚至在乎两个对象是否是实例,所以实现-isEqual:-hash同class同学 他们应该能够调用-isEqual:或者-hashtypesid任何variables,并获得预期的结果。

-isEqual:不同(它可以访问两个被比较的实例),- -hash必须返回一个“盲目”的结果,只访问特定实例中的数据。 由于它不知道散列正在被用于什么,所以对于所有可能被认为是相同/相同的情况,结果必须是一致的,并且必须始终与-isEqual:一致(编辑:这已经被下面的答案揭穿了,它肯定会让生活更轻松)。而且,编写好的散列函数并不重要 – 保证唯一性是一个挑战,特别是当你只有一个NSUInteger(32/64位)在其中代表它。

问题

  1. 实施平等比较时是否有最佳做法?
  2. 在Objective-C和Cocoa-esquecollections中有没有什么特别的计划?
  3. unit testing有没有什么好的方法 – 有合理程度的自信?
  4. 任何关于实现的build议-hash同意-isEqual:包含任意types元素的集合? 我应该知道哪些缺陷? ( 编辑:不像我第一次想到的那样有问题 – 正如@kperryua指出的那样,“equal -hash并不意味着-isEqual: ”)。

编辑: 我应该澄清,我没有对如何实现-isEqual:或-isEqualTo …混淆集合,这是直截了当的。 我认为我的困惑主要来自(错误地)认为-hash必须返回不同的值,如果-isEqual:返回NO。 在过去做了密码学之后,我一直认为不同值的哈希值必须不同。 然而,下面的答案让我意识到,一个“好的”散列函数实际上是关于最小化桶冲突和链接使用-hash集合。 虽然独特的哈希值是可取的,但并不是严格的要求。

我认为试图想出一些通常有用的散列函数,将会为集合生成独特的散列值,这是徒劳的。 U62将所有内容的哈希结合起来的build议不会很好地扩展,因为它使得哈希函数O(n)成为可能。 散列函数实际上应该是O(1)以确保良好的性能,否则散列的目的就被打败了。 (考虑一下plists常见的Cocoa结构,它们是包含数组和其他字典的字典,可能是令人厌恶的,如果集合的哈希函数是O(),那么试图获得大型plist的顶级字典的哈希将是极其慢的。 N)。)

我的build议是不要担心集合的散列很多。 如您所述, -isEqual:意味着相等的-hash值。 另一方面,相等的-hash并不意味着 – -isEqual: 这个事实给了你很大的创造一个简单的散列的余地。

如果你真的担心碰撞(而且你已经证实了真实情况的具体测量结果 ,那么确实值得担心),你仍然可以在某种程度上遵循U62的build议。 例如,您可以采用集合中第一个和/或最后一个元素的散列,并将其与集合的-count结合使用。 这足以提供一个体面的散列。

我希望至less有一个问题的答案。

至于第一:实施-isEqual:非常干净。 你枚举的内容,并检查isEqual:在每个元素。

有一件事要小心,这可能会影响你决定为你的collections' -hashfunction做什么。 您collections的客户还必须了解有关-isEqual:-hash的规则。 如果在集合的-hash使用内容“ -hash ,则如果内容为“ isEqual: ”,则集合将中断isEqual: -hash不同意。 这当然是客户的错,但是这是另一个反对把你的collections内容-hash论点。

第二种是含糊的。 不知道你在那里有什么。

如果两个集合包含相同的元素,则两个集合应该被认为是相等的,而且如果这些集合是有序的,那么元素的顺序是相同的。

关于哈希集合的问题,应该足以以某种方式组合元素的哈希(XOR或模添加它们)。 请注意,尽pipe规则规定两个根据IsEqual相等的对象需要返回相同的散列,但相反并不成立:虽然散列的唯一性是可取的,但解决scheme的正确性并不是必须的。 因此,有序集合不需要考虑元素的顺序。

从苹果文件摘录的方式是一个必要的限制。 对象无法在突变下保持相同的散列值,同时也确保具有相同值的对象具有相同的散列。 这适用于最简单的对象以及集合。 当然,只有当一个对象的哈希位于使用哈希来组织它的元素的容器中时,它才会发生变化。 所有这一切的结果是,可变集合放置在另一个容器中时不应该变异,但是也不应该有任何具有真正的哈希函数的对象。

我已经对NSArray和NSMutableArray默认哈希实现进行了一些调查,并且(除非我误解了某些内容),像苹果这样的接口不遵循他们自己的规则:

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

这是我的testing代码

 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方法的默认实现那样接缝,是数组的计数,它不会在乎它是否在一个集合中。