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

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


当前回答

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

这里有一些关键点:

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

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

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

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

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

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

其他回答

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

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

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

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

等号契约和散列契约在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没有等效的方法。

对关键属性的哈希值进行简单的XOR就足够了 99%的情况下。

例如:

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

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

请注意,如果创建的对象在创建后可以更改,则如果该对象插入到集合中,则哈希值不能更改。实际上,这意味着哈希值必须从初始对象创建时开始固定。更多信息请参阅Apple的NSObject协议的-hash方法文档:

If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. Therefore, either the hash method must not rely on any of the object’s internal state information or you must make sure the object’s internal state information does not change while the object is in the collection. Thus, for example, a mutable dictionary can be put in a hash table but you must not change it while it is in there. (Note that it can be difficult to know whether or not a given object is in a collection.)

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