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

你如何正确地覆盖isEqual:在Objective-C?“陷阱”似乎是，如果两个对象相等(由isEqual:方法确定)，它们必须具有相同的哈希值。

可可基础指南的自省部分确实有一个关于如何覆盖名为MyWidget的类的isEqual:的示例，复制如下:

- (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这样的结构?

(大脑屁:最初将它们与|=一起写成“按位或”。意味着添加。)

94534 次浏览
小开

简单但效率低的方法是为每个实例返回相同的-hash值。否则，是的，您必须仅基于影响相等性的对象实现哈希。如果你在-isEqual:中使用松散的比较(例如不区分大小写的字符串比较)，这是很棘手的。对于整型，你通常可以使用整型本身，除非你要和NSNumbers比较。

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

随机有趣的事实:[[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]，但[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]。(rdar://4538282, 2006年5月5日开始营业)

小开

我发现这个页面是重写等号和哈希类型方法的有用指南。它包括一个计算哈希码的不错的算法。这个页面是面向Java的，但是很容易适应Objective-C/Cocoa。

小开

这并没有直接回答你的问题，但我之前使用MurmurHash生成哈希:murmurhash

我想我应该解释一下原因:低语是非常快的……

小开
最佳答案

开始

 NSUInteger prime = 31;
NSUInteger result = 1;

然后对于每一个原始元素

 result = prime * result + var

对于对象，你用0表示nil，否则它们的hashcode。

 result = prime * result + [var hash];

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

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

解释与归因

这不是tcurdt的作品，评论要求更多的解释，所以我相信编辑归因是公平的。

这个算法是在《Effective Java》一书中普及的，相关章节目前可以在这里找到。那本书普及了该算法，它现在是许多Java应用程序(包括Eclipse)的默认算法。然而，它起源于一个更古老的实现，它被不同程度地归因于Dan Bernstein或Chris Torek。旧的算法最初在Usenet上流传，并且很难确定归属。例如，有一些这个Apache代码中有有趣的注释(搜索它们的名称)引用原始源。

最重要的是，这是一个非常古老，简单的哈希算法。它不是性能最好的，甚至在数学上也没有被证明是一个“好”算法。但它很简单，而且很多人长期使用它，效果很好，所以它有很大的历史支持。

小开

我自己只是在学习Objective-C，所以我不能特别地为这种语言说话，但在我使用的其他语言中，如果两个实例是“相等的”，它们必须返回相同的哈希值——否则当你试图将它们作为哈希表(或任何字典类型的集合)中的键时，你会遇到各种各样的问题。

另一方面，如果两个实例不相等，它们可能具有也可能不具有相同的哈希值——最好不是这样。这就是在哈希表上进行O(1)搜索和O(N)搜索的区别——如果你所有的哈希都发生冲突，你可能会发现搜索你的表并不比搜索一个列表好。

在最佳实践方面，您的哈希应该返回输入值的随机分布。这意味着，例如，如果您有一个double，但您的大多数值倾向于聚集在0到100之间，您需要确保这些值返回的哈希值在整个可能的哈希值范围内均匀分布。这将极大地提高你的表现。

有很多哈希算法，包括这里列出的几个。我尽量避免创建新的哈希算法，因为它可能会有很大的性能影响，所以使用现有的哈希方法并像您在示例中所做的那样按位进行某种组合是避免这种情况的好方法。

小开

注意，如果你正在创建一个在创建后可以改变的对象，如果该对象被插入到一个集合中，哈希值必须不会改变。实际上，这意味着哈希值必须从初始对象创建时开始固定。更多信息见苹果关于NSObject协议的-hash方法的文档:

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

对我来说，这听起来完全是无稽之谈，因为它可能会有效地降低哈希查找的效率，但我认为最好还是谨慎行事，并遵循文档所说的。

小开

我也是Objective C的新手，但我在Objective C 在这里中找到了一篇关于身份与平等的优秀文章。从我的阅读来看，似乎您可以只保留默认的哈希函数(它应该提供唯一的标识)并实现isEqual方法，以便它比较数据值。

小开

Quinn错误地认为对杂音散列的引用在这里是无用的。Quinn说得对，你想要理解哈希背后的理论。低语将很多理论提炼成一个实现。弄清楚如何将该实现应用到这个特定的应用程序是值得研究的。

这里有一些关键点:

tcurdt的示例函数表明，'31'是一个很好的乘数，因为它是质数。我们需要证明质数是充要条件。事实上，31(和7)可能不是特别好的质数，因为31 == -1 % 32。一个奇数的乘数，大约有一半的位被设置，一半的位被清除，可能会更好。(杂音哈希乘法常量具有该属性。)

如果在相乘之后，通过shift和xor调整结果值，这种类型的哈希函数可能会更强。乘法倾向于在寄存器的高端产生大量位交互的结果，而在寄存器的低端产生低交互的结果。shift和xor增加了寄存器底部的交互作用。

将初始结果设置为一个值，其中大约一半的位为0，大约一半的位为1，也会很有用。

注意元素组合的顺序可能是有用的。首先应该处理布尔值和其他值不是强分布的元素。

在计算的最后添加几个额外的位置乱阶段可能是有用的。

对于这个应用程序，杂音散列是否真的快是一个悬而未决的问题。杂音散列预混每个输入字的位。多个输入字可以并行处理，这有助于多问题流水线cpu。

小开
如果我冒着听起来像个彻头彻尾的科学家的风险，我很抱歉，但是…… .．.没有人费心提到，为了遵循“最佳实践”，你绝对不应该指定一个不会考虑目标对象拥有的所有数据的equals方法，例如，无论什么数据聚合到你的对象，而不是它的关联，在实现equals时都应该考虑在内。 如果你不想在比较中考虑'age'，那么你应该写一个比较器并使用它来执行比较，而不是isEqual:.

如果您定义了一个isEqual:方法来任意执行相等比较，那么一旦您忘记了equals解释中的“扭曲”，您就会冒这个方法被其他开发人员甚至您自己误用的风险。

因此，虽然这是一个关于哈希的很好的问题，你通常不需要重新定义哈希方法，你可能应该定义一个特别的比较器。

小开

我发现这个线程非常有用，它提供了我用一个catch实现isEqual:和hash方法所需的一切。当测试isEqual:中的对象实例变量时，示例代码使用:

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

这个反复失败(即。，返回没有)没有和错误，当我<我> < / i >知道对象在我的单元测试中是相同的。原因是，其中一个NSString实例变量是零，所以上面的语句是:

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

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

[nil isEqual: nil]

返回零，也就是没有，所以当被测试对象和被测试对象都有一个零对象时，它们将被认为是不相等的(即。， isEqual:将返回没有)。

这个简单的修复是将if语句更改为:

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

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

我希望这能让一些人少挠头几分钟。

小开

哈希函数应该创建一个不太可能与另一个对象的哈希值冲突或匹配的半唯一值。

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

如果不同对象的结果为0，则会有碰撞散列的风险。当使用一些依赖于哈希函数的集合类时，碰撞哈希会导致意外的程序行为。请确保在使用之前测试您的哈希函数。

-(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;
}
小开

等等，当然一个更简单的方法是首先覆盖- (NSString )description并提供对象状态的字符串表示(你必须在这个字符串中表示对象的整个状态)。

然后，只需提供以下hash的实现:

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

这是基于这样的原则:“如果两个字符串对象相等(由isEqualToString:方法决定)，它们必须具有相同的散列值。”

来源:NSString类引用

小开

记住，你只需要在isEqual为真时提供相等的哈希值。当isEqual为false时，哈希值不一定是不相等的，尽管它可能是不相等的。因此:

保持哈希简单。选择一个(或几个)成员变量是最有特色的。

例如，对于CLPlacemark，只有名称就足够了。是的，有2或3个不同的CLPlacemark具有完全相同的名称，但这是罕见的。使用这个散列。

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


@implementation CLPlacemark (equal)

.．.

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




@end

注意，我没有指定城市、国家等。名字就足够了。也许是名称和CLLocation。

散列应该是均匀分布的。所以你可以使用^ (xor号)来组合几个成员变量

这就像

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

这样哈希将被均匀分布。

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

那么在数组中要做什么呢?

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

小开

等号契约和散列契约在Java世界中有很好的指定和深入的研究(参见@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的子类YourWidget:

- (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;
}

这个实现避免了Apple示例isEqual:中的一些子类化陷阱:

  • 苹果的类测试other isKindOfClass:[self class]对于MyWidget的两个不同子类来说是不对称的。等号需要对称:当且仅当b=a时，a=b。这可以很容易地通过将测试更改为other isKindOfClass:[MyWidget class]来解决，然后所有MyWidget子类将相互比较。
  • 使用isKindOfClass:子类测试可以防止子类用改进的相等性测试重写isEqual:。这是因为相等性需要具有传递性:如果a=b且a=c，则b=c。如果一个MyWidget实例比较等于两个YourWidget实例，那么这两个YourWidget实例必须彼此比较相等，即使它们的serialNo不同。

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

然而，确实有一些情况下isKindOfClass:测试更可取。这在框架类中比应用程序类更典型。例如，任何NSString应该与任何其他具有相同底层字符序列的NSString进行比较，而不管NSString/NSMutableString的区别，也不管NSString类集群中涉及哪些私有类。

在这种情况下，isEqual:应该具有定义良好的、记录良好的行为，并且应该清楚地说明子类不能重写此行为。在Java中，“不重写”限制可以通过将equals和hashcode方法标记为final来强制执行，但Objective-C没有等效的方法。

小开

结合@tcurdt的答案和@oscar-gomez对获取属性名的答案，我们可以为isEqual和hash创建一个简单的解决方案:

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);
}
小开
对关键属性的哈希值进行简单的异或就足够了 99%的时间。

例如:

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

Mattt Thompson在http://nshipster.com/equality/找到的解决方案(也在他的帖子中提到了这个问题:~)


提交答案