重写isEqual的最佳实践：和散列

如何正确地重写isEqual:在Objective-C中？ “catch”似乎是，如果两个对象相等（由isEqual:方法确定），它们必须具有相同的散列值。

Cocoa Fundamentals Guide的Introspection部分有一个关于如何覆盖isEqual:的例子isEqual:复制如下，名为MyWidget的类：

 - (BOOL)isEqual:(id)other { if (other == self) return YES; if (!other || ![other isKindOfClass:[self class]]) return NO; return [self isEqualToWidget:other]; } - (BOOL)isEqualToWidget:(MyWidget *)aWidget { if (self == aWidget) return YES; if (![(id)[self name] isEqual:[aWidget name]]) return NO; if (![[self data] isEqualToData:[aWidget data]]) return NO; return YES; } 

它检查指针是否相等，然后是类的相等性，最后使用isEqualToWidget:比较对象，它只检查name和data属性。 示例没有显示的是如何重写hash 。

假设还有其他一些不影响平等的属性，比如说age 。 不应该重写hash方法，只有name和data会影响哈希？ 如果是的话，你会怎么做？ 只需添加name和data的哈希？ 例如：

 - (NSUInteger)hash { NSUInteger hash = 0; hash += [[self name] hash]; hash += [[self data] hash]; return hash; } 

这足够吗？ 有更好的技术吗？ 如果你有像int这样的基元呢？ 转换他们到NSNumber得到他们的哈希？ 或像NSRect结构？

（ 脑屁 ：本来写的是“按位或”，它们和|=一起加上。）

Answer 1

从…开始

  NSUInteger prime = 31; NSUInteger result = 1; 

那么对于你所做的每一个原始

  result = prime * result + var 

对于64位，你可能也想换个xor。

  result = prime * result + (int) (var ^ (var >>> 32)); 

对于你使用零的对象，否则他们的哈希码。

  result = prime * result + [var hash]; 

对于布尔值，你使用两个不同的值

  result = prime * result + (var)?1231:1237; 

---

解释和归属

这不是我们的工作，并且有意见要求更多解释，所以我认为对归因的编辑是公平的。

该algorithm在“Effective Java”一书中得到了推广， 相关章节目前可以在这里find 。 这本书推广了这个algorithm，现在在许多Java应用程序（包括Eclipse）中都是默认的algorithm。 然而，它来源于一个更为古老的实现，这个实现可以归因于丹·伯恩斯坦（Dan Bernstein）或克里斯·托雷克（Chris Torek） 原来的algorithm最初是围绕Usenet浮现的，而且某些归因是困难的。 例如， 这个Apache代码中有一些有趣的注释 （search它们的名字）引用了原始的源代码。

底线是，这是一个非常古老的，简单的哈希algorithm。 它不是最高性能的，并且在math上甚至不被certificate是“好”的algorithm。 但是很简单，很多人用了很长时间，效果很好，所以有很多历史的支持。

Answer 2

我只是自己捡起Objective-C，所以我不能专门为这种语言说话，但是在其他语言中，如果两个实例是“相等的”，他们必须返回相同的散列值，否则您将拥有全部当尝试将它们用作散列表（或任何字典types集合）中的键时出现问题。

另一方面，如果两个实例不相等，它们可能会或可能不会有相同的哈希值 – 最好是不这样做。 这是一个哈希表上的O（1）search和O（N）search之间的区别 – 如果你所有的哈希碰撞你可能会发现，search你的表没有search列表好。

就最佳实践而言，您的哈希值应该为其input返回值的随机分布。 这意味着，例如，如果您有双精度值，但大多数值趋于在0和100之间进行聚类，则需要确保这些值返回的散列均匀分布在整个可能的散列值范围内。 这将显着提高你的performance。

这里有一些哈希algorithm，其中包括几个在这里列出。 我尝试避免创build新的哈希algorithm，因为它可能会有很大的性能影响，所以使用现有的哈希方法并按照您在示例中进行的某种按位组合进行操作是一种避免它的好方法。

Answer 3

我发现这个线程非常有用，提供了我需要的一切，以获得我的isEqual:和一个捕获实现hash方法。 在isEqual:testing对象实例variables时isEqual:示例代码使用：

 if (![(id)[self name] isEqual:[aWidget name]]) return NO; 

当我知道在我的unit testing中的对象是相同的时候，这个反复失败（ 即返回NO ）没有错误。 原因是，其中一个NSString实例variables是零，所以上面的语句是：

 if (![nil isEqual: nil]) return NO; 

由于零将回应任何方法，这是完全合法的，但

 [nil isEqual: nil] 

返回nil ，这是NO ，所以当对象和正在testing的对象都有一个零对象时，它们将被认为是不相等的（ 即 isEqual:将返回NO ）。

这个简单的解决方法是将if语句更改为：

 if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]]) return NO; 

这样，如果它们的地址是相同的，则跳过方法调用，无论它们是否都是零或者都指向相同的对象，但是如果其中任一个不是零，或者它们指向不同的对象，则适当地调用比较器。

我希望这可以节省一些人头几分钟的抓挠。

Answer 4

在关键属性的哈希值上进行简单的XOR就足够了99％的时间。

例如：

 - (NSUInteger)hash { return [self.name hash] ^ [self.data hash]; } 

解决scheme在http://nshipster.com/equality/由Mattt Thompson（在他的文章中也提到了这个问题！

Answer 5

散列函数应该创build一个不可能碰撞或匹配另一个对象的散列值的半唯一值。

这里是完整的哈希函数，可以适应您的类实例variables。 它使用NSUInteger而不是int来兼容64/32位应用程序。

如果对于不同的对象，结果变为0，则存在碰撞哈希的风险。 在处理依赖哈希函数的一些集合类时，碰撞哈希会导致意外的程序行为。 确保在使用之前testing你的散列函数。

 -(NSUInteger)hash { NSUInteger result = 1; NSUInteger prime = 31; NSUInteger yesPrime = 1231; NSUInteger noPrime = 1237; // Add any object that already has a hash function (NSString) result = prime * result + [self.myObject hash]; // Add primitive variables (int) result = prime * result + self.primitiveVariable; // Boolean values (BOOL) result = prime * result + self.isSelected?yesPrime:noPrime; return result; } 

Answer 6

这帮了我很多！ 可能是你寻找的答案。 实行平等和散列

Answer 7

简单而低效的方法是为每个实例返回相同的-hash值。 否则，是的，您必须仅基于影响相等的对象来实现哈希。 如果在-isEqual:使用宽松比较，这是非常棘手的-isEqual:例如不区分大小写的string比较）。 对于整数，你通常可以使用int本身，除非你将比较NSNumbers。

不要使用| =，但是，它会饱和。 改用^ =。

随机趣事实： [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]] ，但是[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash] 。 （rdar：// 4538282，自2006年5月5日开放）

Answer 8

请记住，只有当isEqual为true时，才需要提供相同的哈希值。 当isEqual为false时，哈希不一定是不相等的，尽pipe大概是这样。 因此：

保持散列简单。 select一个最有特色的成员（或less数成员）variables。

例如，对于CLPlacemark，名字就够了。 是的，有两个或三个区别CLPlacemark与完全相同的名称，但这些是罕见的。 使用该散列。

 @interface CLPlacemark (equal) - (BOOL)isEqual:(CLPlacemark*)other; @end @implementation CLPlacemark (equal) 

…

 -(NSUInteger) hash { return self.name.hash; } @end 

注意我不打扰明确城市，国家等。名字就够了。 也许名字和CLLocation。

散列应该均匀分布。 所以你可以使用^符号组合多个成员variables（xor符号）

所以这是类似的

 hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash 

这样散列将被均匀分布。

 Hash must be O(1), and not O(n) 

那么在数组中做什么？

再一次，简单。 您不必散列数组的所有成员。 足以散列第一个元素，最后一个元素，数量，也许一些中间元素，就是这样。

Answer 9

坚持下去，一个更简单的方法是首先重写- (NSString )description并提供对象状态的string表示（必须在此string中表示对象的整个状态）。

然后，只要提供下面的hash实现：

 - (NSUInteger)hash { return [[self description] hash]; } 

这是基于“如果两个string对象相同（由isEqualToString：方法确定），它们必须具有相同的散列值”。

来源： NSString类参考

Answer 10

这并不直接回答你的问题（根本），但我曾经使用MurmurHash生成哈希： murmurhash

猜我应该解释为什么：murmurhash是血腥的快速…

Answer 11

我发现这个页面是覆盖equals和hashtypes方法的有用指南。 它包括一个体面的哈希码计算algorithm。 该页面是面向Java的，但它很容易适应Objective-C / Cocoa。

Answer 12

我也是一个Objective C的新手，但是我在这里发现了Objective C中一个关于身份与平等的优秀文章。 从我的阅读看来，你可能只能保持默认的哈希函数（应提供一个唯一的身份），并实现isEqual方法，以便它比较数据值。

Answer 13

在Java世界中，equals和hash协议是很好的指定和深入的研究（参见@ mipardi的答案），但Objective-C也应该考虑同样的考虑。

Eclipse在Java中生成这些方法是一个可靠的工作，所以下面是一个手动移植到Objective-C的Eclipse示例：

 - (BOOL)isEqual:(id)object { if (self == object) return true; if ([self class] != [object class]) return false; MyWidget *other = (MyWidget *)object; if (_name == nil) { if (other->_name != nil) return false; } else if (![_name isEqual:other->_name]) return false; if (_data == nil) { if (other->_data != nil) return false; } else if (![_data isEqual:other->_data]) return false; return true; } - (NSUInteger)hash { const NSUInteger prime = 31; NSUInteger result = 1; result = prime * result + [_name hash]; result = prime * result + [_data hash]; return result; } 

对于添加属性serialNo的子类serialNo ：

 - (BOOL)isEqual:(id)object { if (self == object) return true; if (![super isEqual:object]) return false; if ([self class] != [object class]) return false; YourWidget *other = (YourWidget *)object; if (_serialNo == nil) { if (other->_serialNo != nil) return false; } else if (![_serialNo isEqual:other->_serialNo]) return false; return true; } - (NSUInteger)hash { const NSUInteger prime = 31; NSUInteger result = [super hash]; result = prime * result + [_serialNo hash]; return result; } 

这个实现避免了样本isEqual:中的一些子类陷阱isEqual:从Apple：

• 苹果的类testingother isKindOfClass:[self class]对于MyWidget两个不同的子类是不对称的。 平等需要是对称的：a = b当且仅当b = a。 通过将testing更改为other isKindOfClass:[MyWidget class] ，可以很容易地解决这个问题，那么所有的MyWidget子类都可以相互比较。
• 使用isKindOfClass:子类testing可防止子类重写isEqual:使用精确的相等性testing。 这是因为平等需要传递：如果a = b和a = c，那么b = c。 如果一个MyWidget实例比较等于两个YourWidget实例，那么这些YourWidget实例必须相互比较，即使它们的serialNo不同。

第二个问题可以通过只考虑对象是否属于完全相同的类来解决，因此这里的[self class] != [object class]testing。 对于典型的应用程序类 ，这似乎是最好的方法。

但是，当然有些情况下isKindOfClass: test是可取的。 这是比应用程序类更典型的框架类。 例如，无论NSString / NSMutableString区别是什么，任何NSString都应该与具有相同底层字符序列的任何其他NSString相同，也不pipeNSString类集群中涉及哪些私有类。

在这种情况下， isEqual:应该有明确的，logging良好的行为，应该明确的是，子类不能覆盖这个。 在Java中，可以通过将equals和hashcode方法标记为final来强制执行“不覆盖”限制，但是Objective-C没有等效。

Answer 14

将@ tcurdt的答案和@ oscar-gomez的答案结合起来得到属性名称 ，我们可以为isEqual和hash创build一个简单的下拉解决scheme：

 NSArray *PropertyNamesFromObject(id object) { unsigned int propertyCount = 0; objc_property_t * properties = class_copyPropertyList([object class], &propertyCount); NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount]; for (unsigned int i = 0; i < propertyCount; ++i) { objc_property_t property = properties[i]; const char * name = property_getName(property); NSString *propertyName = [NSString stringWithUTF8String:name]; [propertyNames addObject:propertyName]; } free(properties); return propertyNames; } BOOL IsEqualObjects(id object1, id object2) { if (object1 == object2) return YES; if (!object1 || ![object2 isKindOfClass:[object1 class]]) return NO; NSArray *propertyNames = PropertyNamesFromObject(object1); for (NSString *propertyName in propertyNames) { if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName]) && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO; } return YES; } NSUInteger MagicHash(id object) { NSUInteger prime = 31; NSUInteger result = 1; NSArray *propertyNames = PropertyNamesFromObject(object); for (NSString *propertyName in propertyNames) { id value = [object valueForKey:propertyName]; result = prime * result + [value hash]; } return result; } 

现在，在您的自定义类中，您可以轻松实现isEqual:和hash ：

 - (NSUInteger)hash { return MagicHash(self); } - (BOOL)isEqual:(id)other { return IsEqualObjects(self, other); } 

Answer 15

请注意，如果要创build可在创build后进行变更的对象，则如果对象被插入到集合中，则哈希值不得更改 。 实际上，这意味着散列值必须从最初的对象创build点开始固定。 有关更多信息，请参阅Apple对NSObject协议的-hash方法的文档 ：

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

对我来说，这听起来像是一个彻头彻尾的混乱，因为它可能有效地使哈希查找的效率低得多，但我认为最好谨慎一些，并遵循文档所述。

Answer 16

奎因是错误的，在这里杂音散列的参考是无用的。 Quinn是正确的，你想了解哈希背后的理论。 这个杂音将很多这个理论提炼出来。 搞清楚如何将这个实现应用到这个特定的应用程序是值得探索的。

这里的一些关键点：

tcurdt的示例函数表明“31”是一个好的乘数，因为它是素数。 需要说明的是，素质是一个必要和充分的条件。 实际上，31（和7）可能不是特别好的素数，因为31 == -1％32.一个奇数的乘法器，大约一半的位和一半的位清除可能会更好。 （杂音散列常数有这个属性。）

如果在乘法之后，通过shift和xor调整结果值，这种散列函数可能会更强。 乘法往往会在寄存器的高端产生很多位相互作用的结果，而在寄存器的低端产生低的相互作用结果。 shift和xor增加了寄存器底端的相互作用。

将初始结果设置为大约一半位为零且大约一半位为一的值也将趋于有用。

小心组合元素的顺序可能是有用的。 人们应该首先处理布尔值和其他值不是很强的元素。

在计算结束时添加一些额外的比特加扰级可能是有用的。

对于这个应用程序来说杂音散列是否真的很快是一个悬而未决的问题。 杂音散列预混每个input词的位。 多个input字可以并行处理，这有助于多重发出stream水线的cpus。

Answer 17

对不起，如果我冒险听起来这里是一个完整的boffin，但是……没有人提到要遵循“最佳实践”，你绝对不应该指定一个不考虑目标对象拥有的所有数据的equals方法，数据是聚合到你的对象，而不是它的一个关联，应该考虑到实现等于。 如果你不想在比较中考虑“年龄”，那么你应该写一个比较器，用它来比较而不是isEqual :.

如果您定义了一个isEqual：方法来任意执行相等比较，那么一旦您忘记了平等解释中的“扭曲”，就会招致另一个开发人员甚至自己滥用这种方法的风险。

Ergo，虽然这是一个关于散列的很好的问题，但通常不需要重新定义散列方法，您应该定义一个专门的比较器。