你如何isEqual:在Objective-C中正确覆盖？"catch"似乎是如果两个对象相等(由isEqual:方法确定),它们必须具有相同的散列值.
" 可可基础指南"的 " 内省"部分确实有一个示例,说明如何为名为的类重写,如下所示:isEqual: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.
比方说,让我们假设有其他属性不会影响平等age.如果没有hash方法被覆盖,使得只有name和data影响哈希？如果是这样,你会怎么做？只需添加的哈希name和data？例如:
- (NSUInteger)hash {
NSUInteger hash = 0;
hash += [[self name] hash];
hash += [[self data] hash];
return hash;
}
那够了吗？有更好的技术吗？如果你有基元怎么样int？转换它们以NSNumber获取它们的哈希值？或结构像NSRect？
(脑屁:最初写的是"按位或"它们|=.添加.)添加.)
从...开始
NSUInteger prime = 31; NSUInteger result = 1;
然后为你做的每一个原始
result = prime * result + var
对于64位,你可能也想转移和xor.
result = prime * result + (int) (var ^ (var >>> 32));
对于对象,您使用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,所以我不能专门用这种语言说话,但在我使用的其他语言中,如果两个实例是"Equal",它们必须返回相同的哈希值 - 否则你将拥有所有尝试将它们用作哈希表(或任何字典类型集合)中的键时出现的各种问题.
另一方面,如果2个实例不相等,它们可能具有相同的哈希,也可能不具有相同的哈希值 - 如果它们不相同则最好.这是哈希表上的O(1)搜索和O(N)搜索之间的区别 - 如果你的所有哈希冲突,你可能会发现搜索你的表并不比搜索列表更好.
就最佳实践而言,哈希应返回其输入值的随机分布.这意味着,例如,如果您有一个double,但是您的大多数值倾向于在0到100之间聚类,则需要确保这些值返回的哈希值均匀分布在整个可能的哈希值范围内.这将显着提高您的表现.
有许多哈希算法,包括这里列出的几个.我试图避免创建新的哈希算法,因为它可能具有很大的性能影响,因此使用现有的哈希方法并按照您的示例中的某种方式进行按位组合是一种避免它的好方法.
关键属性的哈希值的简单XOR在99%的时间内是足够的.
例如:
- (NSUInteger)hash
{
return [self.name hash] ^ [self.data hash];
}
解决方法是在Mattt Thompson的http://nshipster.com/equality/上找到的(在他的帖子中也提到了这个问题!)
我发现我需要让我的这个主题非常有帮助提供一切isEqual:和hash一个抓落实的方法.在isEqual:示例代码中测试对象实例变量时使用:
if (![(id)[self name] isEqual:[aWidget name]])
return NO;
当我知道单元测试中的对象相同时,这反复失败(即返回NO)没有错误.原因是,其中一个实例变量是零,所以上面的陈述是:NSString
if (![nil isEqual: nil])
return NO;
并且由于nil会对任何方法做出回应,这是完全合法的
[nil isEqual: nil]
返回零,这是NO,因此,当被测试的两种物体和一个有一个零它们将被认为是不相等(对象即,isEqual:将返回NO).
这个简单的解决方法是将if语句更改为:
if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
return NO;
这样,如果它们的地址是相同的,它会跳过方法调用,无论它们是否都是nil或两者都指向同一个对象,但如果它们不是nil或它们指向不同的对象,则适当地调用比较器.
我希望这可以节省几分钟的头部刮伤.
哈希函数应创建一个半唯一值,该值不可能与另一个对象的哈希值冲突或匹配.
这是完整的哈希函数,可以适应您的类实例变量.它使用NSUInteger而不是int来兼容64/32bit应用程序.
如果不同对象的结果为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;
}
简单但低效的方法是-hash为每个实例返回相同的值.否则,是的,您必须仅基于影响相等性的对象实现散列.如果你使用松弛比较-isEqual:(例如不区分大小写的字符串比较),这很棘手.对于int,你通常可以使用int本身,除非你要与NSNumbers进行比较.
不要使用| =,但它会饱和.使用^ =代替.
随意有趣的事实:[[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]但是[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash].(rdar:// 4538282,自2006年5月5日开放)
请记住,只有在isEqual真实时才需要提供相等的哈希值.当isEqual为假时,哈希不必是不相等的,尽管可能是这样.因此:
保持哈希简单.选择最有特色的成员(或少数成员)变量.
例如,对于CLPlacemark,名称就足够了.是的,有两个或三个区别的CLPlacemark具有完全相同的名称,但这些很少见.使用该哈希.
@interface CLPlacemark (equal) - (BOOL)isEqual:(CLPlacemark*)other; @end @implementation CLPlacemark (equal)
...
-(NSUInteger) hash
{
return self.name.hash;
}
@end
请注意,我不打算指定城市,国家等.名称就足够了.也许名称和CLLocation.
哈希应该均匀分布.所以你可以使用插入符号^(xor符号)组合几个成员变量
所以它就像是
hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash
这样哈希将均匀分布.
Hash must be O(1), and not O(n)
那么在阵列中做什么？
再一次,简单.您不必散列数组的所有成员.足以散列第一个元素,最后一个元素,计数,也许是一些中间元素,就是这样.
坚持下去,当然更简单的方法是首先覆盖- (NSString )description并提供对象状态的字符串表示(您必须在此字符串中表示对象的整个状态).
然后,只提供以下实现hash:
- (NSUInteger)hash {
return [[self description] hash];
}
这是基于以下原则:"如果两个字符串对象相等(由isEqualToString:方法确定),它们必须具有相同的散列值."
来源:NSString类参考
我发现这个页面是覆盖equals-和hash-type方法的有用指南.它包括一个计算哈希码的合适算法.该页面面向Java,但很容易使它适应Objective-C/Cocoa.
这并没有直接回答你的问题(根本没有),但我之前使用过MurmurHash来产生哈希:murmurhash
猜猜我应该解释为什么:murmurhash血腥快......
在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;
}
对于YourWidget添加属性的子类serialNo:
- (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;
}
这种实现避免了isEqual:Apple 样本中的一些子类陷阱:
Apple的类测试other isKindOfClass:[self class]对于两个不同的子类是不对称的MyWidget.平等需要是对称的:当且仅当b = a时,a = b.通过将测试更改为可以很容易地解决这个问题other isKindOfClass:[MyWidget class],然后所有MyWidget子类都可以相互比较.
使用isKindOfClass:子类测试可以防止子类覆盖isEqual:精细的相等性测试.这是因为平等需要是可传递的:如果a = b且a = c则b = c.如果MyWidget实例比较等于两个YourWidget实例,则这些YourWidget实例必须相互比较,即使它们serialNo不同.
如果对象属于完全相同的类,则只考虑对象是相等的,因此可以修复第二个问题,因此在[self class] != [object class]此进行测试.对于典型的应用程序类,这似乎是最好的方法.
但是,肯定存在isKindOfClass:优选测试的情况.这是框架类比应用程序类更典型的.例如,任何NSString应该NSString与相同的基础字符序列进行比较等于其他任何其他字符序列,无论NSString/ NSMutableString区别如何,并且无论NSString涉及类集群中的私有类如何.
在这种情况下,isEqual:应该有明确定义的,记录良好的行为,并且应该明确指出子类不能覆盖它.在Java中,可以通过将equals和hashcode方法标记为强制来实现"无覆盖"限制final,但Objective-C没有等价物.
京公网安备 11010802040832号 | 京ICP备19059560号-6 