objective-c - 覆盖 isEqual: 和 hash 的最佳实践

Question

您如何isEqual:在 Objective-C 中正确覆盖？“捕获”似乎是，如果两个对象相等（由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:，它只检查nameanddata属性。该示例未显示的是如何覆盖hash.

让我们假设还有其他不影响相等性的属性，比如age。不应该hash重写该方法以便仅name影响data散列吗？如果是这样，你会怎么做？只需添加和的哈希name值data？例如：

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

这足够了吗？有没有更好的技术？如果你有原语怎么办，比如int？将它们转换NSNumber为获取它们的哈希？或类似的结构NSRect？

（Brain fart：最初将它们与|=. 一起写为“按位或”。意思是添加。）

score 114 · Accepted Answer

从...开始

 NSUInteger prime = 31;
 NSUInteger result = 1;

然后对于你做的每一个原语

 result = prime * result + var

对于对象，您使用 0 表示 nil，否则使用它们的哈希码。

 result = prime * result + [var hash];

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

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

解释和归属

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

该算法在《Effective Java》一书中进行了普及，目前可以在此处在线找到相关章节。那本书普及了该算法，现在该算法已成为许多 Java 应用程序（包括 Eclipse）的默认设置。然而，它源自一个更古老的实现，该实现被各种归因于 Dan Bernstein 或 Chris Torek。那个较旧的算法最初在 Usenet 上流传，并且很难确定归属。例如，这段 Apache 代码中有一些有趣的注释（搜索它们的名字），它们引用了原始源代码。

底线是，这是一个非常古老、简单的散列算法。它不是性能最好的，甚至在数学上也没有被证明是一个“好”的算法。但它很简单，很多人用了很久，效果也不错，所以有很多历史支持。

score 81 · Accepted Answer

我自己只是在学习 Objective-C，所以我不能专门为那种语言说话，但是在我使用的其他语言中，如果两个实例“相等”，它们必须返回相同的哈希 - 否则你将拥有所有尝试将它们用作哈希表（或任何字典类型集合）中的键时会出现各种问题。

另一方面，如果 2 个实例不相等，它们可能具有也可能不具有相同的散列 - 最好不要。这是哈希表上的 O(1) 搜索和 O(N) 搜索之间的区别 - 如果所有哈希都发生冲突，您可能会发现搜索表并不比搜索列表好。

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

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

score 31 · Accepted Answer

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

例如：

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

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

score 27 · Accepted Answer

我发现这个线程非常有用，它提供了一次捕获实现我的方法所需的一切isEqual:。在示例代码hash中测试对象实例变量时使用：isEqual:

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

当我知道单元测试中的对象相同时，这反复失败（即返回NO）而没有错误。原因是，其中一个实例变量是nil，所以上面的语句是：NSString

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或者它们指向不同的对象，则适当地调用比较器。

我希望这可以节省几分钟的时间。

score 22 · Accepted Answer

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

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

score 12 · Accepted Answer

简单但低效的方法是为每个实例返回相同的-hash值。否则，是的，您必须仅基于影响相等性的对象实现散列。如果您在-isEqual:（例如不区分大小写的字符串比较）中使用松散的比较，这会很棘手。对于 int，您通常可以使用 int 本身，除非您将与 NSNumbers 进行比较。

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

随机有趣的事实：[[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]，但是[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]。（rdar://4538282，自 2006 年 5 月 5 日起开放）

score 9 · Accepted Answer

isEqual请记住，您只需要在为真时提供相等的散列。当isEqual为假时，散列不一定是不相等的，尽管它可能是不相等的。因此：

保持哈希简单。选择最有特色的成员（或少数成员）变量。

例如，对于 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)

那么在数组中该怎么做呢？

再次，简单。您不必散列数组的所有成员。足以散列第一个元素，最后一个元素，计数，也许是一些中间元素，仅此而已。

score 8 · Accepted Answer

equals 和 hash 契约在 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:Apple 示例中的一些子类化陷阱：

Apple 的类测试other isKindOfClass:[self class]对于MyWidget. 等式需要是对称的：a=b 当且仅当 b=a。这可以通过将测试更改为来轻松解决other isKindOfClass:[MyWidget class]，然后所有MyWidget子类都可以相互比较。
使用isKindOfClass:子类测试可以防止子类isEqual:被精细的相等测试覆盖。这是因为相等性需要传递：如果 a=b 且 a=c 则 b=c。如果一个MyWidget实例比较等于两个YourWidget实例，那么这些YourWidget实例必须相互比较，即使它们serialNo不同。

第二个问题可以通过仅考虑属于完全相同的类的对象相等来解决，因此[self class] != [object class]这里进行测试。对于典型的应用程序类，这似乎是最好的方法。

但是，在某些情况下isKindOfClass:测试更可取。这比应用程序类更典型的框架类。例如，任何应该与具有相同基础字符序列的NSString任何其他进行比较，而不管/区别如何，也不管类簇中涉及哪些私有类。NSStringNSStringNSMutableStringNSString

在这种情况下，isEqual:应该有明确定义、有据可查的行为，并且应该明确子类不能覆盖它。在 Java 中，可以通过将 equals 和 hashcode 方法标记为来强制执行“不覆盖”限制final，但 Objective-C 没有等效项。

score 7 · Accepted Answer

等等，当然，更简单的方法是首先覆盖- (NSString )description并提供对象状态的字符串表示（您必须在此字符串中表示对象的整个状态）。

然后，只需提供以下实现hash：

- (NSUInteger)hash {
    return [[self description] hash];
}

这是基于“如果两个字符串对象相等（由 isEqualToString: 方法确定），它们必须具有相同的哈希值”的原则。

来源：NSString 类参考

score 5 · Accepted Answer

我发现此页面是覆盖等于和哈希类型方法的有用指南。它包括一个体面的算法来计算哈希码。该页面面向 Java，但很容易将其调整为 Objective-C/Cocoa。

score 5 · Accepted Answer

这并没有直接回答你的问题（根本），但我之前使用过 MurmurHash 来生成哈希：murmurhash

我想我应该解释一下原因：murmurhash 太快了……

score 4 · Accepted Answer

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

score 3 · Accepted Answer

Quinn 错了，这里对 murmur 哈希的引用是无用的。Quinn 说得对，您想了解散列背后的理论。杂音将很多理论提炼成一个实现。弄清楚如何将该实现应用到这个特定的应用程序是值得探索的。

这里的一些关键点：

来自 tcurdt 的示例函数表明 '31' 是一个很好的乘数，因为它是素数。人们需要证明，成为素数是一个充要条件。事实上，31（和 7）可能不是特别好的素数，因为 31 == -1 % 32。一个奇数乘数，大约一半的位被设置，一半的位被清除可能会更好。（杂音散列乘法常数具有该属性。）

如果在乘法之后通过移位和异或调整结果值，这种类型的哈希函数可能会更强。乘法往往会在寄存器的高端产生大量位交互的结果，而在寄存器的底端产生低交互的结果。移位和异或增加了寄存器底端的交互。

将初始结果设置为大约一半位为零且大约一半位为一的值也往往是有用的。

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

在计算结束时添加几个额外的比特加扰阶段可能很有用。

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

请注意，如果您正在创建一个可以在创建后发生变异的对象，那么如果将对象插入到集合中，则哈希值不得更改。实际上，这意味着哈希值必须从初始对象创建的那一刻开始固定。有关更多信息，请参阅Apple 关于 NSObject 协议的 -hash 方法的文档：

如果将可变对象添加到使用哈希值确定对象在集合中的位置的集合中，则当对象在集合中时，对象的哈希方法返回的值不得更改。因此，散列方法不能依赖任何对象的内部状态信息，或者您必须确保对象在集合中时对象的内部状态信息不会改变。因此，例如，可以将可变字典放入哈希表中，但您不能在其中更改它。（请注意，很难知道给定对象是否在集合中。）

这对我来说听起来很奇怪，因为它可能会有效地降低哈希查找的效率，但我认为最好谨慎行事并遵循文档所说的内容。

score 1 · Accepted Answer

抱歉，如果我冒着在这里听起来完全的风险，但是... ...没有人打扰提到要遵循“最佳实践”，您绝对不应该指定一个不会考虑目标对象拥有的所有数据的 equals 方法，例如任何数据聚合到你的对象，而不是它的关联，在实现 equals 时应该考虑到。如果您不想在比较中考虑“年龄”，那么您应该编写一个比较器并使用它来执行比较，而不是使用 isEqual:。

如果您定义了一个任意执行相等比较的 isEqual: 方法，一旦您忘记了对等式解释中的“扭曲”，您就会面临该方法被其他开发人员甚至您自己滥用的风险。

因此，虽然这是一个关于散列的很好的问答，但您通常不需要重新定义散列方法，您可能应该定义一个临时比较器。

objective-c - 覆盖 isEqual: 和 hash 的最佳实践

16 回答 16

解释和归属

Related

Reference