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

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

Cocoa Fundamentals Guide的Introspection部分确实有一个关于如何重写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:比较对象，后者只检查名称和数据属性。这个例子没有说明如何重写哈希。

让我们假设有其他属性不影响平等，比如年龄。难道不应该重写哈希方法，以便只有名称和数据影响哈希吗?如果是，你会怎么做?只是添加名称和数据的散列吗?例如:

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

这足够了吗?有更好的技术吗?如果你有基本类型，比如int呢?将它们转换为NSNumber以获得它们的散列?或者像NSRect这样的结构?

(脑屁:最初把“位或”和|=写在一起。意味着添加。)

当前回答

等号契约和散列契约在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;
}

对于一个子类YourWidget，它添加了一个属性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: from Apple示例中的一些子类化陷阱:

Apple's class test other isKindOfClass:[self class] is asymmetric for two different subclasses of MyWidget. Equality needs to be symmetric: a=b if and only if b=a. This could easily be fixed by changing the test to other isKindOfClass:[MyWidget class], then all MyWidget subclasses would be mutually comparable. Using an isKindOfClass: subclass test prevents subclasses from overriding isEqual: with a refined equality test. This is because equality needs to be transitive: if a=b and a=c then b=c. If a MyWidget instance compares equal to two YourWidget instances, then those YourWidget instances must compare equal to each other, even if their serialNo differs.

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

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

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

2013-05-19 10:32:42

其他回答

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

2009-02-24 15:04:49

等号契约和散列契约在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;
}

对于一个子类YourWidget，它添加了一个属性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: from Apple示例中的一些子类化陷阱:

2013-05-19 10:32:42

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

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

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

2008-10-31 17:34:06

我发现这个线程非常有帮助，提供了我需要的一切来获得我的isEqual:和哈希方法实现了一个捕获。当测试isEqual中的对象实例变量时:示例代码使用:

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

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

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

因为nil会响应任何方法，这是完全合法的，但是

[nil isEqual: nil]

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

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

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

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

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

2010-11-26 19:21:01

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

这里有一些关键点:

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

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

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

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

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

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

2009-08-31 19:02:29

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

推荐文章

最新文章

标签