為什么要有isEqual方法
對于對象類型, ==運算符比較的是對象的地址，即是否為同一對象西傀。
對象地址相等不代表對象相等斤寇，即對象地址相等是對象相等的必要非充分條件。
isEqual方法就是用來判斷兩個對象是否相等池凄。
isEqual的默認實現
isEqual方法是NSObject中聲明的抡驼，默認實現就是簡單的比較對象地址。
@implementation NSObject (Approximate)
- (BOOL)isEqual:(id)object {
return self == object;
}
@end
NSObject的子類可以實現自己的isEqual:方法肿仑，一般方式如下：
- 實現新的
isEqualTo__ClassName__:方法致盟，用來做具體屬性值的對比碎税，我們叫做高層比較方法 - 重載
isEqual:,先做對象地址的比較，以及對象類型的比較馏锡，然后調用高層比較方法 - 重載
hash:,這個方法后面再講
如果是集合類型的話雷蹂，還應該做深度判等，即所有成員一一進行比較杯道。
綜合舉例如下：
@implementation NSArray (Approximate)
- (BOOL)isEqualToArray:(NSArray *)array {
if (!array || [self count] != [array count]) {
return NO;
}
for (NSUInteger idx = 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:[NSArray class]]) {
return NO;
}
return [self isEqualToArray:(NSArray *)object];
}
@end
在Foundation中匪煌，很多NSObject的子類已經定義好了自己的isEqual，及其高層比較方法：
- NSAttributedString -isEqualToAttributedString:
- NSData -isEqualToData:
- NSDate -isEqualToDate:
- NSDictionary -isEqualToDictionary:
- NSHashTable -isEqualToHashTable:
- NSIndexSet -isEqualToIndexSet:
- NSNumber -isEqualToNumber:
- NSOrderedSet -isEqualToOrderedSet:
- NSSet -isEqualToSet:
- NSString -isEqualToString:
- NSTimeZone -isEqualToTimeZone:
- NSValue -isEqualToValue:
NSArray中isEqual相關實踐
看一段示例代碼
NSString* name1 = @"小明";
NSMutableArray* array = [NSMutableArray arrayWithObjects:name1,nil];
NSString* name2 = [NSString stringWithFormat:@"小明"];
NSLog(@"name1:%p,name2:%p",name1,name2);
NSLog(@"[array contain:name2]=%d",[array containsObject:name2]);
[array removeObject:name2];
NSLog(@"[array remove:name2].count=%zd",array.count);
打印結果
name1:0x108e58200,name2:0x600000436780
[array contain:name2]=1
[array remove:name2].count=0
可見党巾，NSArray的containsObject:和removeObject:方法都是使用了isEqual來判斷成員是否相等的萎庭。removeObject:會把所有相等的成員都移除掉。
為什么要有hash方法
我們在數組中查找某個成員齿拂，在數組未排序的情況下, 查找的時間復雜度是O(array_length)
為了提高查找的速度, Hash Table出現了驳规。當成員被加入到Hash Table中時, 會給它分配一個hash值, 以標識該成員在集合中的位置，通過這個位置標識可以將查找的時間復雜度優(yōu)化到O(1), 當然如果多個成員都是同一個位置標識, 那么查找就不能達到O(1)了
重點來了:
分配的這個hash值(即用于查找集合中成員的位置標識), 就是通過hash方法計算得來的, 且hash方法返回的hash值最好唯一
和數組相比, 基于hash值索引的Hash Table查找某個成員的過程就是
Step 1: 通過hash值直接找到查找目標的位置
Step 2: 如果目標位置上有多個相同hash值得成員, 此時再按照數組方式進行查找
hash方法什么時候被調用?
HashTable是一種基本的數據結構署海，NSSet和NSDictionary都是使用了HashTable存儲數據吗购，因此可以確保它們查詢成員的速度為O(1)。而NSArray使用了順序表存儲數據砸狞，查詢速度為O(n)捻勉。
hash方法只在對象被添加至NSSet和設置為NSDictionary的key時會調用
NSSet添加新成員時, 需要根據hash值來快速查找成員, 以保證集合中是否已經存在該成員
NSDictionary在查找key時, 也利用了key的hash值來提高查找的效率
hash和isEqual的關系
- 對象的判等是相互的 ([a isEqual:b] ? [b isEqual:a])
- 如果兩個對象相等，那么它們的hash值一定相等 ([a isEqual:b] ? [a hash] == [b hash])
- 值相等刀森，兩個對象不一定相等 ([a hash] == [b hash] ?? [a isEqual:b])
總之踱启，hash值是對象判等的必要非充分條件
為了優(yōu)化判等的效率, 基于hash的NSSet和NSDictionary在判斷成員是否相等時, 會這樣做
Step 1: 集成成員的hash值是否和目標hash值相等, 如果相同進入Step 2, 如果不等, 直接判斷不相等
Step 2: hash值相同(即Step 1)的情況下, 再進行對象判等, 作為判等的結果
如何重寫自己的hash方法
hash方法是NSObject中聲明的，默認實現是返回對象的內存地址研底。
那么hash方法的最佳實踐到底是什么呢?
大神Mattt Thompson在Equality中給出的結論就是
In reality, a simple XOR over the hash values of critical properties is sufficient 99% of the time(對關鍵屬性的hash值進行位異或運算作為hash值)
比如對于Person類的hash方法實現如下
- (NSUInteger)hash {
return [self.name hash] ^ [self.birthday hash];
}
