重写 isEqual： 和 hash 的最佳做法

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

但是不要使用 |=，它会饱和。请改用 ^=。

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

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

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

我想我应该解释一下原因：murmurhash 是血腥的......

入手

 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 代码中有一些有趣的注释（搜索它们的名称）引用了原始源代码。

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

我自己只是拿起 Objective-C，所以我不能专门代表该语言，但在我使用的其他语言中，如果两个实例“相等”，它们必须返回相同的哈希值 - 否则，当尝试将它们用作哈希表（或任何字典类型集合）中的键时，您将遇到各种问题。

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

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

市面上有许多哈希算法，包括这里列出的几种。我尽量避免创建新的哈希算法，因为它可能会对性能产生很大影响，因此使用现有的哈希方法并执行某种按位组合（如示例中所示）是避免这种情况的好方法。

请注意，如果要创建可在创建后进行更改的对象，则在将对象插入集合时，哈希值不得更改。实际上，这意味着哈希值必须从初始对象创建点开始固定。有关详细信息，请参阅 Apple 关于 NSObject 协议的 -hash 方法的文档：

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

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

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

Quinn 错了，这里对杂音哈希的引用毫无用处。Quinn说得对，你想了解哈希背后的理论。杂音将许多理论提炼成一种实现。弄清楚如何将该实现应用于此特定应用程序是值得探索的。

以下是一些关键点：

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

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

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

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

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

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

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

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

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

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

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 对象时，它们将被视为不相等（即返回 NO）。isEqual:

这个简单的解决方法是将 if 语句更改为：

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

这样，如果它们的地址相同，则无论它们是否都指向同一对象，它都会跳过方法调用，但如果它们不是 nil 或它们指向不同的对象，则适当地调用比较器。

我希望这能为某人节省几分钟的挠头时间。

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

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

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

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

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

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

来源： NSString 类参考

请记住，您只需要提供在 true 时相等的哈希值。当为 false 时，哈希值不必不相等，尽管它可能是不相等的。因此：isEqualisEqual

保持哈希简单。选择一个（或几个成员）最独特的成员变量。

例如，对于 CLPlacemark，仅名称就足够了。是的，有 2 或 3 个名称完全相同的不同 CLPlacemark，但这些都很少见。使用该哈希值。

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

@implementation CLPlacemark (equal)

...

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


@end

请注意，我懒得指定城市、国家等。这个名字就足够了。也许是名称和 CLLocation。

哈希值应均匀分布。因此，您可以使用插入符号 ^（异或符号）组合多个成员变量

所以它类似于

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

这样，哈希值将均匀分布。

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

那么在数组中做什么呢？

再次，简单。您不必对数组的所有成员进行哈希处理。足以对第一个元素、最后一个元素、计数，也许还有一些中间元素进行哈希处理，仅此而已。

在 Java 世界中，equals 和 hash 合约被很好地指定和深入研究（参见 @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;
}

对于添加属性的子类：YourWidgetserialNo

- (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;
}

此实现避免了 Apple 示例中的一些子类陷阱：isEqual:

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

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

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

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

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

对关键属性的哈希值进行简单的异或就足够了 99% 的时间。

例如：

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

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