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

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


当前回答

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

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

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

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

其他回答

我发现这个线程非常有帮助,提供了我需要的一切来获得我的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或它们指向不同的对象,则会适当地调用比较器。

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

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

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

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

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

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

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

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