Note:下面的问题是相关的,但它们和相关资源似乎都不能完全回答我的问题,尤其是关于对collections of objects实施平等测试的问题.
- Best practices for overriding -isEqual: and -hash
- Techniques for implementing -hash on mutable Cocoa objects
出身背景
NSObject提供了-hash
(返回实例地址,如(NSUInteger)self
)和-isEqual:
(返回NO
,除非接收器地址和参数相同)的default个实现.这些方法被设计为在必要时被重写,但文档明确指出,您应该同时提供这两种方法,或者两者都不提供.此外,如果-isEqual:
针对两个对象返回YES
,那么针对这些对象must的-hash
的结果将是相同的.如果不是,那么当将本应相同的对象(例如-compare:
返回NSOrderedSame
的两个字符串实例)添加到Cocoa集合或直接进行比较时,就会出现问题.
上下文
我开发了CHDataStructures.framework,一个Objective-C数据 struct 的开源库.我已经实现了许多集合,目前正在改进和增强它们的功能.我想添加的一个功能是能够比较集合是否与其他集合相等.
这些比较应该只考虑两个集合中存在的对象(包括排序,如果适用的话),而不只是比较内存地址.这种方法在可可中有相当多的先例,通常使用单独的方法,包括以下方法:
-[NSArray isEqualToArray:]
-[NSDate isEqualToDate:]
-[NSDictionary isEqualToDictionary:]
-[NSNumber isEqualToNumber:]
-[NSSet isEqualToSet:]
-[NSString isEqualToString:]
-[NSValue isEqualToValue:]
我想让我的自定义集合对相等性测试具有健壮性,这样它们就可以安全地(且可预测地)添加到其他集合中,并允许其他集合(如NSSet)确定两个集合是否相等/等效/重复.
问题
-isEqualTo...:
方法本身工作得很好,但是定义这些方法的类通常也会重写-isEqual:
以调用[self isEqualTo...:]
,如果参数与接收方属于同一类(或者可能是子类),或者[super isEqual:]
属于其他类.这意味着该类还必须定义-hash
,以便为具有相同内容的不同实例返回相同的值.
此外,苹果-hash
年的文件规定如下:(强调我的)
"If a mutable object is added to a collection that uses hash values to determine the object's position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. Therefore, 100 the hash method must not rely on any of the object's internal state information 101 you must make sure the object's internal state information does not change while the object is in the collection. Thus, for example, a mutable dictionary can be put in a hash table but you must not change it while it is in there. (Note that it can be difficult to know whether or not a given object is in a collection.)"
Edit: I definitely understand why this is necessary and totally agree with the reasoning — I mentioned it here to provide additional context, and skirted the topic of why it's the case for the sake of brevity.
我的所有集合都是可变的,散列必须考虑至少some的内容,所以这里唯一的 Select 是考虑它是一个编程错误来改变在另一个集合中存储的集合.(我的Collection 都采用了NSCopying本,所以像NSDictionary这样的Collection 可以成功地复制一本用作密钥等.)
对我来说,实现-isEqual:
和-hash
是有意义的,因为(例如)我的一个类的间接用户可能不知道要调用的特定-isEqualTo...:
方法,甚至不关心两个对象是否是同一个类的实例.他们应该能够对id
类型的任何变量调用-isEqual:
或-hash
,并得到预期的结果.
与-isEqual:
不同(-isEqual:
可以访问两个被比较的实例),-hash
必须"盲目"返回结果,只能访问特定实例中的数据因为它不知道散列的用途,所以all个可能的实例的结果必须一致,这些实例应被视为相等/相同,并且必须始终与-isEqual:
一致.(Edit: This has been debunked by the answers below, and it certainly makes life easier.)此外,编写好的散列函数非常重要——保证唯一性是一个挑战,尤其是当您只有一个整数(32/64位)来表示它时.
问题
- 在对集合执行
相等比较时,是否有最佳做法? - 在Objective-C和Cocoa-esque系列中有什么特别之处需要计划吗?
- 对于单元测试
-hash
,有没有可靠的方法? - 对于包含任意类型元素的集合,有没有关于实现
-hash
以同意-isEqual:
的建议?我应该知道哪些trap ?(Edit:并不像我最初想的那样有问题——正如@kperryua所指出的,"等于-hash
的值意味着-isEqual:
".)
Edit: I should have clarified that I'm not confused about how to implement -isEqual: or -isEqualTo...: for collections, that's straightforward. I think my confusion stemmed mainly from (mistakenly) thinking that -hash MUST return a different value if -isEqual: returns NO. Having done cryptography in the past, I was thinking that hashes for different values MUST be different. However, the answers below made me realize that a "good" hash function is really about minimizing bucket collisions and chaining for collections that use 100. While unique hashes are preferable, they are not a strict requirement.