实施-hash / -isEqual：/ -isEqualTo ...：对Objective-C的集

注：以下SO问题是相关的，但他们及链接的资源，似乎完全回答我的问题，特别是有关实施平等试验对象的集合 。

用于覆盖-isEqual最佳实践：与-hash
对可变Cocoa对象实施-hash技术

背景

NSObject的提供的默认的实现-hash （它返回该实例的地址，例如(NSUInteger)self ）和-isEqual:返回NO除非接收器的地址，并且所述参数是相同的）。这些方法旨在覆盖作为必要的，但文件清楚地表明，你应该同时提供或者两者都不是。此外，如果-isEqual:返回YES两个对象，然后的结果-hash那些对象必须是相同的。如果不是这样，当对象应该是相同的问题接踵而至能-例如两个字符串实例为其中-compare:返回NSOrderedSame -被添加到可可收集或直接进行比较。

上下文

我开发CHDataStructures.framework ，Objective-C的数据结构的一个开源库。我已经实现了一些藏品，和我目前正在不断改善和加强其功能。有一个问题我想添加的功能是比较收藏与另一平等的能力。

而不是只比较内存地址，这些比较应考虑存在于两个集合的对象（包括订购，如果适用）。这种方法具有在可可相当先例，通常使用一个独立的方法，其中包括以下内容：

-[NSArray isEqualToArray:]
-[NSDate isEqualToDate:]
-[NSDictionary isEqualToDictionary:]
-[NSNumber isEqualToNumber:]
-[NSSet isEqualToSet:]
-[NSString isEqualToString:]
-[NSValue isEqualToValue:]

我想我的自定义集合强大的平等的测试，所以他们可以安全地（和可预测）被加入到其他收藏品，并允许其他人（如一个NSSet中）来确定两个集合是否相等/当量/重复。

问题

一个-isEqualTo...:方法适用于自己的伟大，但定义这些方法的类通常还覆盖-isEqual:调用[self isEqualTo...:]如果参数是同一类的（或者子类）作为接收器，或[super isEqual:]否则。这意味着类也必须定义-hash ，这样它将返回具有相同内容不同的情况下，相同的值。

此外，苹果的文档-hash规定了以下内容：（重点煤矿）

“如果一个可变对象被添加到使用的散列值，以确定该对象的集合中的位置的集合，由对象的哈希方法返回的值不能而所述对象是所述集合中的变化。因此， 无论是散列法必须不依赖于任何对象的内部状态信息，或者您必须确保当对象是集合中的对象的内部状态信息不会改变。因此，例如，一个可变字典可以放在一个哈希表，但你必须而它在那里不改变它。（请注意，它可能很难知道一个给定的对象是否是一个集合中）。”

编辑： 我绝对明白为什么这是必要的，并与推理完全同意-我在这里提到它提供额外的上下文和回避的原因是为了简洁起见情况的话题。

我所有的藏品都是可变的，哈希将不得不考虑至少部分的内容，所以在这里唯一的选择就是认为这是一个编程错误变异储存在另一个集合的集合。（我的收藏品全部采用NSCopying ，所以喜欢的NSDictionary的集合可以成功地进行复制的钥匙，等使用）

这是有道理的，我来实现-isEqual:和-hash ，因为（举例来说）我的课可能不知道具体的一个间接用户-isEqualTo...:方法来调用，甚至照顾两个对象是否实例同一类别。他们应该能够调用-isEqual:或-hash对类型的任何变量id并获得预期的结果。

不像-isEqual:它可以访问两个实例进行比较）， -hash必须返回一个结果“盲目地”，与特定的实例中只访问该数据。 ~~因为它无法知道正在使用什么哈希，其结果必然是应该考虑的平等/相同的所有可能的情况一致，且必须始终同意-isEqual:~~ （编辑：这是通过下面的答案揭穿，也肯定让生活更轻松）。此外，编写好的哈希函数是不平凡-保证唯一性是一个挑战，尤其是当你只有一个NSUInteger（32/64位）在其中表示它。

问题

有没有实现~~平等的比较~~时的最佳实践-hash的收藏？
是否有任何特别之处在Objective-C和可可式的集合计划？
有没有什么好的方法进行单元测试-hash与合理的置信度？
在实施任何建议-hash与同意-isEqual:包含任意类型的元素集合？我应该知道什么陷阱？（ 编辑：我首先想到的不是有问题-因为@kperryua指出，“等于-hash值并不意味着-isEqual: ”。）

编辑： 我应该澄清，我不是困惑如何实现-isEqual：或-isEqualTo ...：用于收藏，这是简单的。 我想，我的困惑主要来自（错误地）以为-hash必须返回如果-isEqual不同的值：返回NO。 做完加密在过去，我在想，对于散列值不同必须是不同的。 但是，下面的答案使我意识到，一个“好”的哈希函数实际上是关于减少桶的碰撞和链接对于使用集合-hash 。 而独特的哈希值是最好，他们不是一个严格的要求。

Answer 1:

我认为，试图想出一些通常是有用的哈希函数，将产生对集合唯一哈希值是徒劳无益的。结合所有内容的散列U62的建议不会很好地扩展，因为它使哈希函数O（n）。 Hash函数应该真正为O（1），以确保良好的性能，否则哈希的目的被击败。（考虑的Plist，它们是含有阵列和其他字典，潜在字典的共同可可构建广告nauseum。试图采取大的plist的顶层字典的散列是，如果集合的散列函数是O：极为缓慢（ N）。）

我的建议是不要担心集合的哈希很大。正如你所说， -isEqual:意味着平等-hash值。在另一方面，等于-hash值并不意味着-isEqual: 这一事实给了你很大的回旋余地，以创建一个简单的哈希值。

如果你真的担心冲突，但（你必须在确认它是值得担忧的现实情况具体测量证明），你仍然可以跟随U62的意见，在一定程度上。例如，你可以采取的，比方说，第一和/或最后一个元素集合中的散列值，并结合起来，与，比方说， -count集合。这足以提供一个体面的哈希值。

我希望您的问题至少答案之一。

至于1号：实现-isEqual:很添油加醋。你列举的内容，并检查isEqual：方法在每个元素。

有一两件事要小心，可能会影响你决定为你的收藏做什么-hash功能。您收藏的用户还必须了解规则管理-isEqual:和-hash 。如果您使用的内容-hash在您的收藏的-hash ，你的收藏将打破，如果的内容isEqual:和-hash不同意。这是客户的错，当然，不过这对你的基础另一种说法-hash离集合的内容。

2号是一种模糊的。不知道你心里有没有。

Answer 2:

两个集合应被认为是相等的，如果他们包含相同的元素，进一步，如果集合是有序的，这些元素都以相同的顺序。

在哈希值对集合的主题，它应该是足够的元素的哈希以某种方式（XOR他们或模添加的话）结合起来。请注意，虽然规则规定，两个对象是根据ISEQUAL等于需要返回相同的散列，相反不成立：尽管哈希的独特性是desireable，没有必要为解决方案的正确性。这样的有序集合不必考虑的元素的顺序。

从苹果文档的摘录的方式一个必要的限制。一个对象不能保持在突变相同的散列值，同时确保使用相同的值对象具有相同的哈希值。这适用于简单的对象以及集合。当然，这只是一般重要的，当它是使用散列来组织它的元素的容器内的对象的哈希值发生变化。所有这一切的结果是，放置在另一个容器中时可变集合不应发生变异，但后来也不应该有一个真正的散列函数的任何对象。

Answer 3:

我做了一些调查到的NSArray和NSMutableArray里默认的哈希实施和（除非我误解的东西），它接缝像苹果不遵守thier自己的规则：

如果一个可变对象添加到使用散列值来确定对象的集合中的位置的集合，而对象是收集由对象的哈希方法返回的值不得改变。因此，无论是散列法决不能依赖于任何对象的内部状态信息，或者您必须在对象是集合中确定对象的内部状态信息不会改变。因此，例如，一个可变字典可以放在一个哈希表，但同时它在那里，你不能改变它。（请注意，它可能很难知道一个给定的对象是否是一个集合中）。

这里是我的测试代码

NSMutableArray* myMutableArray = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
NSMutableArray* containerForMutableArray = [NSMutableArray arrayWithObject:myMutableArray];

NSUInteger hashBeforeMutation = [[containerForMutableArray objectAtIndex:0] hash];
[[containerForMutableArray objectAtIndex:0] removeObjectAtIndex:1];
NSUInteger hashAfterMutation = [[containerForMutableArray objectAtIndex:0] hash];

NSLog(@"Hash Before: %d", hashBeforeMutation);
NSLog(@"Hash After : %d", hashAfterMutation);

输出是：