簡介
Objective-C中峭状，經(jīng)常會有需要重寫- (BOOL)isEuqal:(id)other方法的情況。但是很少有人重寫- (NSUInteger)hash方法劝赔。本文就詳細解釋一下hash方法的用處和不重寫可能出現(xiàn)的問題胆敞。
哈希表
Objective-C中着帽，NSDictionary和NSSet是由哈希表實現(xiàn)的。
在討論哈希表之前移层，先規(guī)范幾個接下來會用到的概念仍翰。哈希表的本質(zhì)是一個數(shù)組，數(shù)組中每一個元素稱為一個箱子(bin)观话，箱子中存放的是需要存儲的對象予借，比如字典中就是鍵值對，集合中就是要放入集合的對象匪燕。
哈希表的存儲過程如下:
根據(jù) key 計算出它的哈希值 h蕾羊。
假設(shè)箱子的個數(shù)為 n，那么這個鍵值對應(yīng)該放在第 (h % n) 個箱子中帽驯。
如果該箱子中已經(jīng)有了鍵值對，就使用開放尋址法或者拉鏈法解決沖突利凑。
在使用拉鏈法解決哈希沖突時牌借，每個箱子其實是一個鏈表适荣，屬于同一個箱子的所有鍵值對都會排列在鏈表中够吩。
哈希表還有一個重要的屬性: 負載因子(load factor)，它用來衡量哈希表的 空/滿 程度湾笛，一定程度上也可以體現(xiàn)查詢的效率，計算公式為:
負載因子 = 總鍵值對數(shù) / 箱子個數(shù)
負載因子越大，意味著哈希表越滿，越容易導(dǎo)致沖突，性能也就越低路捧。因此，一般來說，當負載因子大于某個常數(shù)(可能是 1零渐，或者 0.75 等)時，哈希表將自動擴容。
重寫hash函數(shù)
Objective-C中杀糯，NSObject的默認hash方法實現(xiàn)為：
- (NSUInteger)hash {
return (NSUInteger)self;
}
在實現(xiàn)一個hash函數(shù)的時候固翰，需要技巧的一點是，找出哪個值對于對象來說是關(guān)鍵的。
對于一個 NSDate 對象來說太示，從一個參考日期到它本身的時間間隔就已經(jīng)足夠了：
@implementation NSDate (Approximate)
- (NSUInteger)hash {
return (NSUInteger)abs([self timeIntervalSinceReferenceDate]);
}
對于一個 UIColor 對象邻吭，RGB 元素的移位和可以很方便地計算出來：
@implementation UIColor (Approximate)
- (NSUInteger)hash {
CGFloat red, green, blue;
[self getRed:&red green:&green blue:&blue alpha:nil];
return ((NSUInteger)(red * 255) << 16) + ((NSUInteger)(green * 255) << 8) + (NSUInteger)(blue * 255);
}
@end
綜合上面所說的內(nèi)容，下面是一個在子類中重載默認相等性檢查時可能的實現(xiàn)：
@interface Person
@property NSString *firstName;
@property NSString *lastName;
@property NSDate *birthday;
- (BOOL)isEqualToPerson:(Person *)person;
@end
@implementation Person
- (BOOL)isEqualToPerson:(Person *)person {
if (!person) {
return NO;
}
// ||操作符的操作看起來好像是不必要的，但是如果我們需要處理兩個屬性都是 nil 的情形的話幢尚，它能夠正確地返回 YES。比較像 NSUInteger 這樣的標量是否相等時，則只需要使用 == 就可以了。
BOOL firstNameIsEqual = (self.firstName == person.firstName || [self.firstName isEqual:person.firstName]);
BOOL lastNameIsEqual = (self.lastName == person.lastName || [self.lastName isEqual:person.lastName]);
BOOL haveEqualBirthdays = (self.birthday == person.birthday) || [self.birthday isEqualToDate:person.birthday];
return firstNameIsEqual && lastNameIsEqual && 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.firstName hash] ^ [self.lastName hash] ^ [self.birthday hash];
}
上面的例子中，有一個小問題，因為 ^ 操作是有對稱性的， 即A^B == B^A胳搞，所以如果兩個生日相同的人姑原，一個叫"George Frederick"阴绢，另一個叫"Frederick George"左电，則他們的hash值一樣闰蚕。
為了避免這種情況，我們需要手動打破這種對稱性，比如旋轉(zhuǎn)移位操作。
#define NSUINT_BIT (CHAR_BIT * sizeof(NSUInteger))
#define NSUINTROTATE(val, howmuch) ((((NSUInteger)val) << howmuch) | (((NSUInteger)val) >> (NSUINT_BIT - howmuch)))
- (NSUInteger)hash
{
//這里實際上不需要旋轉(zhuǎn)lastName,這里只是演示多個屬性時怎么處理。同理如果還有一個NSUInteger的屬性，那么兩個NSUInteger的hash值也需要被旋轉(zhuǎn)
return NSUINTROTATE([_firstName hash], NSUINT_BIT / 2) ^ NSUINTROTATE([_lastName hash], NSUINT_BIT / 3) ^ [self.birthday hash];
}
在實現(xiàn)一個hash函數(shù)的時候，一個很常見的誤解來源于認為 hash 得到的值 必須 是唯一可區(qū)分的。實際上娜亿，對于關(guān)鍵屬性的散列值進行一個簡單的XOR操作吼畏，就能夠滿足在 99% 的情況下的需求了躲舌。
何時需要重寫hash
Objective-C中诀拭，重寫了isEqual:方法，一般來說不需要重寫hash方法，但是如果這個對象需要被用作key在字典中存儲時沽瘦，就需要重寫。
現(xiàn)在有People和People2兩個類，代碼如下：
@interface People : NSObject <NSCopying>
@property (nonatomic,copy) NSString *firstName;
@property (nonatomic,copy) NSString *lastName;
@property (nonatomic,assign) NSInteger age;
@end
@implementation People
- (id)copyWithZone:(nullable NSZone *)zone {
return self;
}
- (BOOL)isEqual:(id)object {
if (self == object) {
return YES;
}
if (![object isKindOfClass:[People class]]) {
return NO;
}
return [self isEqualToPeople:object];
}
- (BOOL)isEqualToPeople:(People *)other {
BOOL firstNameIsEqual = (self.firstName == other.firstName || [self.firstName isEqual:other.firstName]);
BOOL lastNameIsEqual = (self.lastName == other.lastName || [self.lastName isEqual:other.lastName]);
BOOL ageIsEqual = (self.age == other.age);
return firstNameIsEqual && lastNameIsEqual && ageIsEqual;
}
#define NSUINT_BIT (CHAR_BIT * sizeof(NSUInteger))
#define NSUINTROTATE(val, howmuch) ((((NSUInteger)val) << howmuch) | (((NSUInteger)val) >> (NSUINT_BIT - howmuch)))
- (NSUInteger)hash
{
//這里實際上不需要旋轉(zhuǎn)lastName,這里只是演示多個屬性時怎么處理棚潦。同理如果還有一個NSUInteger的屬性荚孵，那么兩個NSUInteger的hash值也最好旋轉(zhuǎn)
return NSUINTROTATE([_firstName hash], NSUINT_BIT / 2) ^ NSUINTROTATE([_lastName hash], NSUINT_BIT / 3) ^ (NSUInteger)self.age;
}
@end
People2類和People類一模一樣谒麦，但是沒有重新hash方法√В現(xiàn)在我們以People類的實例來作為key，在字典中存儲一對鍵值對刁赦。代碼如下：
printf("\n---------------- Person類 ----------------\n");
{
People *p1 = [[People alloc] init];
p1.firstName = @"lucy";
p1.lastName = @"Green";
People *p2 = [[People alloc] init];
p2.firstName = @"lucy";
p2.lastName = @"Green";
NSLog(@"p1 = %p, p2 = %p, (p1和p2%@)", p1, p2, [p1 isEqual:p2] ? @"相等" : @"不相等");
BOOL hashEqual = ([p1 hash] == [p2 hash]);
NSLog(@"p1.hash = %ld, p2.hash = %ld, p1.hash %@ p2.hash", [p1 hash], [p2 hash], hashEqual?@"==":@"!=");
NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithDictionary:@{p1:@"value1"}];
NSLog(@"用p2作為key取值 %@",[dict objectForKey:p2]);
}
printf("\n---------------- Person2類 ----------------\n");
{
People2 *p1 = [[People2 alloc] init];
p1.firstName = @"lucy";
p1.lastName = @"Green";
People2 *p2 = [[People2 alloc] init];
p2.firstName = @"lucy";
p2.lastName = @"Green";
NSLog(@"p1 = %p, p2 = %p, (p1和p2%@) ", p1, p2, [p1 isEqual:p2] ? @"相等" : @"不相等");
BOOL hashEqual = ([p1 hash] == [p2 hash]);
NSLog(@"p1.hash = %ld, p2.hash = %ld, p1.hash %@ p2.hash", [p1 hash], [p2 hash], hashEqual?@"==":@"!=");
NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithDictionary:@{p1:@"value1"}];
NSLog(@"用p2作為key取值 %@",[dict objectForKey:p2]);
}
運行上面的代碼，打印結(jié)果揉阎，多打印幾次，這里我列出其中兩次的log情況：
---------------- Person類 ----------------
2017-09-20 17:34:46.820 NSAD[1308:39307] p1 = 0x610000037500, p2 = 0x610000036e60, (p1和p2相等)
2017-09-20 17:34:46.820 NSAD[1308:39307] p1.hash = 2714281438307418121, p2.hash = 2714281438307418121, p1.hash == p2.hash
2017-09-20 17:34:46.820 NSAD[1308:39307] 用p2作為key取值 value1
---------------- Person2類 ----------------
2017-09-20 17:34:46.820 NSAD[1308:39307] p1 = 0x608000035780, p2 = 0x6080000357e0, (p1和p2相等)
2017-09-20 17:34:46.821 NSAD[1308:39307] p1.hash = 106102872299392, p2.hash = 106102872299488, p1.hash != p2.hash
2017-09-20 17:34:46.821 NSAD[1308:39307] 用p2作為key取值 value1
---------------- Person類 ----------------
2017-09-20 17:45:44.665 NSAD[1359:43287] p1 = 0x608000221c00, p2 = 0x608000221ca0, (p1和p2相等)
2017-09-20 17:45:44.666 NSAD[1359:43287] p1.hash = 2714281438307418121, p2.hash = 2714281438307418121, p1.hash == p2.hash
2017-09-20 17:45:44.666 NSAD[1359:43287] 用p2作為key取值 value1
---------------- Person2類 ----------------
2017-09-20 17:45:44.666 NSAD[1359:43287] p1 = 0x600000223c00, p2 = 0x600000223c20, (p1和p2相等)
2017-09-20 17:45:44.667 NSAD[1359:43287] p1.hash = 105553118510080, p2.hash = 105553118510112, p1.hash != p2.hash
2017-09-20 17:45:44.667 NSAD[1359:43287] 用p2作為key取值 (null)
可以看到站粟，兩次log的結(jié)果修械，Person2類的行為不同，第一次可以使用實例p2讀出key為p1的value柬唯，第二次不行。
思考：
為什么Person2類代碼沒有改動涂屁，但是運行結(jié)果會變，第一次可以，第二次不行？
解答：
Person2類的hash方法沒有重寫胞谭，所以p1.hash != p2.hash宛渐。
當p1作為key存儲字典時幔荒，此時會根據(jù)字典的當前“箱子個數(shù)”n糊闽，做 p1.hash % n 操作，算出應(yīng)該存放在第幾個“箱子”爹梁。
再以p2為key取值的時候右犹， 同樣會 p2.hash % n 算要去第幾個“箱子”獲取。找到對應(yīng)的箱子后姚垃，再使用isEqual:方法比較key念链，找到對應(yīng)的value。
因為p1 isEqual: p2，即使 p1.hash != p2.hash, 但是當 (p1.hash % n) == (p2.hash % n) 時掂墓，一樣可以用p2作為key去對字典進行操作谦纱，例如結(jié)果1。 但是如果求余結(jié)果不等君编，則找不到跨嘉，此時就會出現(xiàn)結(jié)果2。
因為默認的hash方法是直接返回的對象的地址吃嘿，也就是說p1和p2的hash值是不可控的祠乃，所以上面的代碼，Person2類的行為是未定義的兑燥。
結(jié)論
綜上所述亮瓷，如果我們重寫了isEqual:方法，大部分情況寫可以不管hash方法降瞳，但是當我們需要把這個類的對象加入一張哈希表中的時候嘱支，我們一定要重新hash方法。
最后在總結(jié)一下equal和hash的關(guān)系挣饥。
- 對象相等具有 交換性
（[a isEqual:b] ? [b isEqual:a]) - 如果兩個對象相等除师，它們的
hash值也一定是相等的([a isEqual:b] ? [a hash] == [b hash]) - 反過來則不然，兩個對象的散列值相等不一定意味著它們就是相等的
([a hash] == [b hash] ?? [a isEqual:b])
本文代碼可以在Github上我的demo中找到亮靴。
參考資料：
Equality - NSHipster
Implementing Equality and Hashing
深入理解哈希表
