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

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


当前回答

Sorry if I risk sounding a complete boffin here but... ...nobody bothered mentioning that to follow 'best practices' you should definitely not specify an equals method that would NOT take into account all data owned by your target object, e.g whatever data is aggregated to your object, versus an associate of it, should be taken into account when implementing equals. If you don't want to take, say 'age' into account in a comparison, then you should write a comparator and use that to perform your comparisons instead of isEqual:.

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

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

其他回答

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

这里是完整的哈希函数,它可以适应你的类实例变量。它使用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;
}

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

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

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

结合@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);
}

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

这里有一些关键点:

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

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

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

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

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

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

Sorry if I risk sounding a complete boffin here but... ...nobody bothered mentioning that to follow 'best practices' you should definitely not specify an equals method that would NOT take into account all data owned by your target object, e.g whatever data is aggregated to your object, versus an associate of it, should be taken into account when implementing equals. If you don't want to take, say 'age' into account in a comparison, then you should write a comparator and use that to perform your comparisons instead of isEqual:.

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

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