重写isEqual:和散列的最佳实践

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

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

当前回答

开始

 NSUInteger prime = 31;
 NSUInteger result = 1;

然后对于每一个原始元素

 result = prime * result + var

对于对象，你用0表示nil，否则它们的hashcode。

 result = prime * result + [var hash];

对于布尔值，使用两个不同的值

 result = prime * result + ((var)?1231:1237);

解释与归因

这不是tcurdt的作品，评论要求更多的解释，所以我相信编辑归因是公平的。

This algorithm was popularized in the book "Effective Java", and the relevant chapter can currently be found online here. That book popularized the algorithm, which is now a default in a number of Java applications (including Eclipse). It derived, however, from an even older implementation which is variously attributed to Dan Bernstein or Chris Torek. That older algorithm originally floated around on Usenet, and certain attribution is difficult. For example, there is some interesting commentary in this Apache code (search for their names) that references the original source.

最重要的是，这是一个非常古老，简单的哈希算法。它不是性能最好的，甚至在数学上也没有被证明是一个“好”算法。但它很简单，而且很多人长期使用它，效果很好，所以它有很大的历史支持。

2008-10-31 17:58:53

其他回答

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

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

2010-12-08 23:44:34

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

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

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

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

2008-10-31 18:27:13

开始

 NSUInteger prime = 31;
 NSUInteger result = 1;

然后对于每一个原始元素

 result = prime * result + var

对于对象，你用0表示nil，否则它们的hashcode。

 result = prime * result + [var hash];

对于布尔值，使用两个不同的值

 result = prime * result + ((var)?1231:1237);

解释与归因

这不是tcurdt的作品，评论要求更多的解释，所以我相信编辑归因是公平的。

2008-10-31 17:58:53

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

2013-10-29 19:24:22

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

2013-05-19 10:32:42

重写isEqual:和散列的最佳实践

推荐文章

最新文章

标签