- 相等的概念是探究哲學(xué)和數(shù)學(xué)的核心，并且對(duì)道德点寥、公正和公共政策的問題有著深遠(yuǎn)的影響艾疟。
從一個(gè)經(jīng)驗(yàn)主義者的角度來看，兩個(gè)物體不能依據(jù)一些觀測(cè)標(biāo)準(zhǔn)中分辨出來敢辩，它們就是相等的蔽莱。在人文方面，平等主義者認(rèn)為相等意味著要保持每個(gè)人的社會(huì)戚长、經(jīng)濟(jì)盗冷、政治和他們住地的司法系統(tǒng)都一致。
對(duì)程序員來說同廉，協(xié)調(diào)好邏輯和感官能力來理解我們塑造的'相同'的語義是一項(xiàng)任務(wù)仪糖。'相同的問題'(的探討)太微妙，同時(shí)有太容易被忽視迫肖。對(duì)語義沒有充分的理解就直接去實(shí)現(xiàn)它锅劝，可能會(huì)導(dǎo)致沒必要的工作和不正確的結(jié)果。因此對(duì)數(shù)學(xué)和邏輯系統(tǒng)的深刻理解與按既定計(jì)劃實(shí)現(xiàn)同樣必要蟆湖。
雖然所有的技術(shù)博文都是有誘惑你來讀它的標(biāo)題和代碼故爵，但請(qǐng)花幾分鐘時(shí)間來閱讀和理解這些文字。逐字地復(fù)制看似有用的代碼而不知道為什么這樣寫很有可能導(dǎo)致一些錯(cuò)誤隅津。相等性是個(gè)重要話題之一诬垂，但它仍包含了許多混亂的概念，尤其是在Objective-C中伦仍。
Equality & Identity
- 首先结窘，弄清楚equality和identity的區(qū)別很重要。
如果兩個(gè)物體具有相同的觀測(cè)屬性呢铆，它們是可以相互等同的晦鞋。但是，這兩個(gè)對(duì)象仍然可以分辨出差異棺克，它們各自的identity。在程序中线定，一個(gè)對(duì)象的identity是和它的內(nèi)存地址關(guān)聯(lián)的娜谊。
NSObject對(duì)象測(cè)試和另一個(gè)對(duì)象是否相同使用isEqual:方法，在它的基本實(shí)現(xiàn)里性等性檢查本質(zhì)上是對(duì)identity的檢查斤讥，如果兩個(gè)對(duì)象指向了相同的內(nèi)存地址纱皆，它們被認(rèn)為是相等的湾趾。
@implementation NSObject(Approximate)
- (BOOL)isEqual:(id)object {
return self== object;
}
@end
- 對(duì)于內(nèi)置的類，像NSArray, NSDictionary, 和 NSString派草，進(jìn)行了一個(gè)深層的相等性比較搀缠，來測(cè)試在集合中的每個(gè)元素是否相等，這是一個(gè)應(yīng)該也確實(shí)非常有用的做法近迁。
NSObject 的子類要實(shí)現(xiàn)它們各自的isEqual:方法時(shí)艺普，應(yīng)該做到以下幾點(diǎn)：
1.實(shí)現(xiàn)一個(gè)isEqualTo__ClassName__:方法來執(zhí)行有意義的值比較.
2.重寫isEqual:方法 來作類型和對(duì)象identity檢查, 回調(diào)上述的值比較方法.
3.重寫 hash, 這個(gè)會(huì)在下一部分解釋.
這里有一個(gè)NSArray實(shí)現(xiàn)這個(gè)的大概的思路(這個(gè)例子忽略了類簇, 實(shí)際實(shí)現(xiàn)會(huì)更具體復(fù)雜):
@implementation NSArray(Approximate)
- (BOOL)isEqualToArray:(NSArray*)array {
if(!array || [selfcount] != [array count]) {
return NO;
}
for(NSUIntegeridx =0; idx < [array count]; idx++) {
if(![self[idx] isEqual:array[idx]]) {
return NO;
}
}
return YES;
}
- (BOOL)isEqual:(id)object {
if(self== object) {
return YES;
}
if(![object isKindOfClass:[NSArrayclass]]) {
return NO;
}
return [selfisEqualToArray:(NSArray*)object];
}
@end
- 下面的在Foudation中NSObject的子類已經(jīng)自定義了判等實(shí)現(xiàn)，用了相關(guān)的方法：
NSAttributedString-isEqualToAttributedString:
NSData-isEqualToData:NSDate-isEqualToDate:
NSDictionary-isEqualToDictionary:
NSHashTable-isEqualToHashTable:
NSIndexSet-isEqualToIndexSet:
NSNumber-isEqualToNumber:
NSOrderedSet-isEqualToOrderedSet:
NSSet-isEqualToSet:
NSString-isEqualToString:
NSTimeZone-isEqualToTimeZone:
NSValue-isEqualToValue:
- 當(dāng)比較任何這些類的兩個(gè)實(shí)例時(shí)鉴竭，推薦使用它們各自的高級(jí)別的
method而不是isEqual:
然而歧譬，我們的理論實(shí)現(xiàn)還沒有完成，現(xiàn)在搏存，讓我們把注意力轉(zhuǎn)向hash（一段插曲：先清理一下NSString的問題）瑰步。
NSString判等的奇怪案例
一個(gè)有趣的插曲，看一下這個(gè)代碼：
NSString *a = @"Hello";
NSString *b =@"Hello";
BOOL wtf = (a == b);
// YES
- 鄭重地聲明一下正確的比較兩個(gè)
NSString對(duì)象相等的方法是使用-isEqualToString:方法璧眠，無論如何也不能通過==操作符來比較兩個(gè)NSString缩焦。
那么這里是怎么回事呢？為什么 NSArray或者NSDictionary字面量相同不會(huì)這樣责静，而它(NSString)會(huì)這樣呢舌界。
這都是一種被稱為字符串駐留的優(yōu)化技術(shù)做的，因?yàn)檫@種優(yōu)化不同的值可以對(duì)一份不可變的字符串值的備份進(jìn)行拷貝泰演。NSString 類型的a指針和b指針對(duì)駐留字符串 @"Hello"進(jìn)行了相同的拷貝呻拌。注意這個(gè)優(yōu)化僅僅對(duì)靜態(tài)聲明的不可變字符串有效。
更有趣的是睦焕，OC的selector的名字也會(huì)被當(dāng)做駐留字符串存儲(chǔ)在一個(gè)共用的字符串pool中藐握。
Hashing
最日常的面向?qū)ο缶幊虂碚f，對(duì)象判等最主要的用法在于決定集合成員垃喊。為了讓這一步更快一些猾普，自定義判等實(shí)現(xiàn)的類應(yīng)該也實(shí)現(xiàn)hash:
1.對(duì)象相等是相互的([a isEqual:b] ? [b isEqual:a])
2.如果對(duì)象相等，它們的hash值必須相等([a isEqual:b] ? [a hash] == [b hash])
但是本谜，反過來不一定成立：如果它們的hash值相等初家，兩個(gè)對(duì)象不一定相等。([a hash] == [b hash] ?? [a isEqual:b])
現(xiàn)在快速翻看一下《計(jì)算機(jī)科學(xué)》101:
hash表式編程中的基本的數(shù)據(jù)結(jié)構(gòu)乌助，它可以使 NSSet & NSDictionary 快速地(O(1))查找它的元素溜在。
我們也可以通過對(duì)比著數(shù)組很好地理解hash表：
Arrays按照有序的索引存儲(chǔ)元素，因此一個(gè)大小為n的數(shù)組會(huì)把元素放在索引1他托，2直到n-1.為了確定數(shù)組中的一個(gè)元素存在了哪里掖肋，不得不一個(gè)個(gè)檢查每個(gè)位置(除非數(shù)組碰巧已經(jīng)排序好，但這是另一回事)赏参。
Hash表使用了略微不同的方法志笼。而不是按順序存儲(chǔ)元素沿盅，hash表在內(nèi)存中分配了n個(gè)位置，同時(shí)用一個(gè)函數(shù)來計(jì)算在這個(gè)范圍內(nèi)計(jì)算一個(gè)位置纫溃。一個(gè)hash函數(shù)是確定性的腰涧，同時(shí)一個(gè)好的hash函數(shù)使用一個(gè)相對(duì)均勻的散列來生成值，而且不會(huì)有太多的計(jì)算過程紊浩。當(dāng)兩個(gè)不同的對(duì)象計(jì)算出相同的hash值時(shí)窖铡，會(huì)產(chǎn)生hash沖突。當(dāng)沖突發(fā)生時(shí)郎楼，hash表會(huì)尋找沖突點(diǎn)同時(shí)把新加的對(duì)象放到第一個(gè)可用的位置万伤。當(dāng)hash表變得越來越擁擠，沖突的可能性會(huì)增加呜袁，這會(huì)導(dǎo)致花費(fèi)更多的時(shí)間來尋找空間(這就是為什么均勻散列的hash函數(shù)不菲的原因敌买。)
一個(gè)關(guān)于實(shí)現(xiàn)hash函數(shù)的錯(cuò)誤共識(shí)來自于隨之發(fā)生的斷言，這個(gè)錯(cuò)誤的共識(shí)認(rèn)為hash值必須是不同的阶界。這個(gè)錯(cuò)誤共識(shí)會(huì)導(dǎo)致不必要地復(fù)雜實(shí)現(xiàn)虹钮，包括從Java textbooks復(fù)制過來的質(zhì)數(shù)的神奇咒語。實(shí)際上膘融，一個(gè)簡(jiǎn)單的對(duì)關(guān)鍵屬性hash值的XOR(異或運(yùn)算)對(duì)于99%的情況來說已經(jīng)夠用了芙粱。
技巧就是思考對(duì)象中的哪個(gè)值是關(guān)鍵的。
對(duì) NSDate 來說氧映，對(duì)參照日期的時(shí)間間隔已經(jīng)夠用了：
@implementation NSDate(Approximate)
- (NSUInteger)hash {
return (NSUInteger) abs ( [self timeIntervalSinceReferenceDate] ) ;
}
- 對(duì)UIColor來說春畔，移位之后的RGB值是非常方便計(jì)算的
@implementation UIColor(Approximate)
- (NSUInteger)hash {
CGFloatred, green, blue;
[selfgetRed:&red green:&green blue:&blue alpha:nil];
return ((NSUInteger)(red *255) <<16) + ((NSUInteger)(green *255) <<8) + (NSUInteger)(blue *255);
}
@end
在子類中實(shí)現(xiàn) -isEqual: 和 hash
- 綜合在一起，這里有一個(gè)如何在子類重寫默認(rèn)的判等實(shí)現(xiàn)的例子：
@interfacePerson
@property NSString*name;
@property NSDate*birthday;
- (BOOL)isEqualToPerson:(Person *)person;
@end
@implementationPerson
- (BOOL)isEqualToPerson:(Person *)person {
if(!person) {
return NO;
}
BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];
return haveEqualNames && haveEqualBirthdays;
}
#pragma mark - NSObject
- (BOOL)isEqual:(id)object {
if(self== object) {
return YES;
}
if(![object isKindOfClass:[Person class]]) {
return NO;
}
return [self isEqualToPerson:(Person *)object];
}
- (NSUInteger)hash {
return [self.name hash] ^ [self.birthday hash];
}@end
- 如果想滿足好奇心或者出于學(xué)究式的研究岛都，看一下這個(gè) Mike Ash的文章律姨，解釋了通過移位和翻轉(zhuǎn)組合值如何改善了可能產(chǎn)生重疊(沖突)的hash.
本文完全翻譯自：http://nshipster.com/equality/
本文轉(zhuǎn)自 https://www.cnblogs.com/Mike-zh/p/5147041.html
