覆盖 isEqual: 和 hash 的最佳实践 [英] Best practices for overriding isEqual: and hash

问题描述

如何在 Objective-C 中正确覆盖 isEqual:?捕获"似乎是如果两个对象相等(由 isEqual: 方法确定)，它们必须具有相同的哈希值.

How do you properly override isEqual: in Objective-C? The "catch" seems to be that if two objects are equal (as determined by the isEqual: method), they must have the same hash value.

Cocoa Fundamentals Guide 的 noreferrer">Introspection 部分确实有关于如何覆盖 isEqual: 的示例，复制如下，用于名为 MyWidget 的类:

The Introspection section of the Cocoa Fundamentals Guide does have an example on how to override isEqual:, copied as follows, for a class named 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:比较对象，只检查name和data属性.示例没有展示的是如何覆盖hash.

It checks pointer equality, then class equality, and finally compares the objects using isEqualToWidget:, which only checks the name and data properties. What the example doesn't show is how to override hash.

让我们假设还有其他不影响相等的属性，比如 age.hash 方法不应该被覆盖，这样只有 name 和 data 会影响哈希吗?如果是这样，你会怎么做?只需添加name 和data 的哈希值?例如:

Let's assume there are other properties that do not affect equality, say age. Shouldn't the hash method be overridden such that only name and data affect the hash? And if so, how would you do that? Just add the hashes of name and data? For example:

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

够了吗?有没有更好的技术?如果你有像 int 这样的原语怎么办?将它们转换为 NSNumber 以获取它们的哈希?或者像 NSRect 这样的结构?

Is that sufficient? Is there a better technique? What if you have primitives, like int? Convert them to NSNumber to get their hash? Or structs like NSRect?

(脑放屁:最初将它们与 |= 一起写成按位或".意思是添加.)

(Brain fart: Originally wrote "bitwise OR" them together with |=. Meant add.)

推荐答案

开始

 NSUInteger prime = 31;
 NSUInteger result = 1;

然后对于你做的每一个基元

Then for every primitive you do

 result = prime * result + var

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

For objects you use 0 for nil and otherwise their hashcode.

 result = prime * result + [var hash];

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

For booleans you use two different values

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

<小时>

解释和归属

这不是 tcurdt 的工作，评论要求提供更多解释，所以我相信对归因进行编辑是公平的.

---

Explanation and Attribution

This is not tcurdt's work, and comments were asking for more explanation, so I believe an edit for attribution is fair.

该算法在《Effective Java》一书中得到普及，相关目前可以在此处在线找到章节.那本书普及了该算法，该算法现在是许多 Java 应用程序(包括 Eclipse)的默认设置.然而，它源自一个更旧的实现，该实现被不同地归因于 Dan Bernstein 或 Chris Torek.那个较旧的算法最初在 Usenet 上流传，并且某些归因是困难的.例如，在这个 Apache 代码中有一些 有趣的评论(搜索他们的名字)引用原始来源.

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.

最重要的是，这是一个非常古老、简单的散列算法.它不是最高效的，甚至在数学上也没有证明它是一个好"的算法.但是它很简单，而且很多人长期使用，效果很好，所以有很多历史支持.

Bottom line is, this is a very old, simple hashing algorithm. It is not the most performant, and it is not even proven mathematically to be a "good" algorithm. But it is simple, and a lot of people have used it for a long time with good results, so it has a lot of historical support.

这篇关于覆盖 isEqual: 和 hash 的最佳实践的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！