Qui*_*lor 47 cocoa equality objective-c chdatastructures data-structures
注意:以下SO问题是相关的,但它们和链接资源似乎都没有完全回答我的问题,特别是在实现对象集合的相等性测试方面.
NSObject提供默认实现-hash(返回实例的地址,如(NSUInteger)self)和-isEqual:(NO除非接收者的地址和参数相同,否则返回).这些方法旨在根据需要进行覆盖,但文档清楚地表明您应该同时提供这两种方法,或者两者都不提供.此外,如果-isEqual:返回YES两个对象,那么-hash这些对象的结果必须相同.如果不是这样,当应该相同的对象(例如两个-compare:返回的字符串实例)NSOrderedSame被添加到Cocoa集合或直接比较时,就会出现问题.
我开发了CHDataStructures.framework,这是一个Objective-C数据结构的开源库.我已经实现了许多集合,目前正在改进和增强其功能.我想要添加的功能之一是能够将集合与另一个集合进行比较.
这些比较不应仅比较内存地址,而应考虑两个集合中存在的对象(包括排序,如果适用).这种方法在Cocoa中具有相当先例,并且通常使用单独的方法,包括以下方法:
-[NSArray isEqualToArray:]-[NSDate isEqualToDate:]-[NSDictionary isEqualToDictionary:]-[NSNumber isEqualToNumber:]-[NSSet isEqualToSet:]-[NSString isEqualToString:]-[NSValue isEqualToValue:]我想使我的自定义集合对于相等性测试具有鲁棒性,因此可以安全地(并且可预测地)将它们添加到其他集合中,并允许其他集合(如NSSet)确定两个集合是否相等/等同/重复.
一个-isEqualTo...:方法本身很有用,但是定义这些方法的类通常也会覆盖-isEqual:调用,[self isEqualTo...:]如果参数与接收者属于同一个类(或者可能是子类),或者[super isEqual:]不是.这意味着类还必须定义-hash,以便为具有相同内容的不同实例返回相同的值.
此外,Apple的文档-hash规定如下:(强调我的)
"如果一个可变对象被添加到使用的散列值,以确定该对象的集合中的位置的集合,由对象的哈希方法返回的值不能而所述对象是所述集合中的变化.因此,任一散列法不能依赖于对象的任何内部状态信息,或者必须确保对象在集合中时对象的内部状态信息不会发生变化.因此,例如,可变字典可以放在哈希表中但是你必须当它在那里时不要改变它.(注意,很难知道给定对象是否在集合中.)"
编辑: 我明白为什么这是必要的并完全同意推理 - 我在这里提到它提供额外的背景,并为了简洁而避开了为什么会这样的主题.
我的所有集合都是可变的,并且散列必须至少考虑一些内容,因此这里唯一的选择是将其视为编程错误来改变存储在另一个集合中的集合.(我的集合都采用NSCopying,因此像NSDictionary这样的集合可以成功地复制用作密钥等)
这是有道理的,我实施-isEqual:和-hash,因为(举例来说)我班的一个间接用户可能不知道具体的-isEqualTo...:方法来调用,甚至照顾两个对象是否是同一类的实例.他们应该能够调用-isEqual:或-hash在任何类型的变量上id获得预期的结果.
与-isEqual:(可以访问两个被比较的实例)不同,-hash必须"盲目地"返回结果,只能访问特定实例中的数据.由于它无法知道正在使用的哈希值,因此结果必须与所有可能被视为相等/相同的实例一致,并且必须始终一致.(编辑:这已经被下面的答案揭穿了,它确实让生活更轻松.)此外,编写好的哈希函数并非易事 - 保证唯一性是一个挑战,特别是当你只有一个NSUInteger(32/64位)时在其中代表它.-isEqual:
-hash？-hash合理的置信度进行单元测试的好方法？-hash同意-isEqual:包含任意类型元素的集合的任何建议？我应该知道哪些陷阱？(编辑:不像我最初想象的那样有问题 - 正如@kperryua指出的那样,"相等的-hash价值并不意味着-isEqual:".)编辑: 我应该澄清一点,我并没有对如何实现-isEqual:或-isEqualTo ...:对于集合实现困惑,这很简单.我认为我的困惑主要源于(错误地)认为-hash必须返回一个不同的值,如果-isEqual:返回NO.在过去完成了加密,我认为不同值的哈希必须是不同的.但是,下面的答案让我意识到"良好"的哈希函数实际上是关于最小化桶冲突和链接使用的集合-hash.虽然独特的哈希值是优选的,但它们并不是严格要求.
kpe*_*yua 18
我想尝试提出一些通常有用的哈希函数,它将为集合生成唯一的哈希值,这是徒劳的.U62关于组合所有内容的散列的建议将不能很好地扩展,因为它使散列函数O(n).散列函数应该确实是O(1)以确保良好的性能,否则散列的目的就会失败.(考虑一下plists的常见Cocoa构造,它是包含数组和其他字典的字典,可能是令人作呕的.如果集合的散列函数是O(如果集合的散列函数是O),尝试获取大plist的顶级字典的散列将会非常慢. N).)
我的建议是不要担心集合的哈希问题.如你所说,-isEqual:暗示相等的-hash价值观.另一方面,同等-hash价值并不意味着-isEqual:.这个事实为你创造一个简单的哈希提供了很大的余地.
如果你真的担心碰撞(并且你已经证明了现实世界情况的具体测量证明了这是令人担心的事情),你仍然可以在某种程度上遵循U62的建议.例如,您可以获取集合中的第一个和/或最后一个元素的哈希值,并将其与集合中的元素相结合-count.这足以提供一个像样的哈希.
我希望至少回答你的一个问题.
至于第1名:实施-isEqual:非常简单和干燥.您枚举内容,并在每个元素上检查isEqual :.
有一点需要注意,这可能会影响您决定为集合的-hash功能做什么.您的馆藏客户还必须了解管理-isEqual:和管理的规则-hash.如果您使用-hash收藏品中的内容-hash,那么您的收藏品将会破坏,如果内容' isEqual:并且-hash不同意.当然,这是客户的错,但这是另一个反对基于-hash集合内容的论据.
2号是模糊的.不知道你有什么想法.