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

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


当前回答

请注意,如果创建的对象在创建后可以更改,则如果该对象插入到集合中,则哈希值不能更改。实际上,这意味着哈希值必须从初始对象创建时开始固定。更多信息请参阅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.)

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

其他回答

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

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

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

请注意,如果创建的对象在创建后可以更改,则如果该对象插入到集合中,则哈希值不能更改。实际上,这意味着哈希值必须从初始对象创建时开始固定。更多信息请参阅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.)

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

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

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

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

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