在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。

其他回答

记住,你只需要在isEqual为真时提供相等的哈希值。当isEqual为false时,散列不一定是不相等的,尽管假设它是不相等的。因此:

保持哈希简单。选择一个(或几个)成员变量是最有特色的。

例如,对于CLPlacemark,只有名称就足够了。是的,有2或3个不同的CLPlacemark具有完全相同的名称,但这是罕见的。使用这个散列。

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

...

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

注意,我没有指定城市、国家等。名字就足够了。也许是名称和CLLocation。

散列应该是均匀分布的。所以你可以使用^ (xor号)来组合几个成员变量

这就像

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

这样哈希将被均匀分布。

Hash must be O(1), and not O(n)

那么在数组中要做什么呢?

再次,简单。你不必hash数组的所有成员。足以散列第一个元素,最后一个元素,计数,也许还有一些中间元素,就这样。

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

这里有一些关键点:

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

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

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

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

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

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

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

例如:

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

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

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

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

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