問題引入
用集合過濾重復(fù)元素
NSString *str1 = @"hello world";
NSString *str2 = [NSString stringWithFormat:@"%@",@"hello world"];
NSMutableSet *s = [[NSMutableSet alloc] init];
[s addObject:str1];
[s addObject:str2];
/*
{(
"hello world"
)}
*/
如果自定義對象Person呢？
@interface Person : NSObject
@property(nonatomic,copy)NSString *name;
@property(nonatomic,assign)NSInteger age;
@end
@implementation Person
-(NSString *)description
{
return [NSString stringWithFormat:@"<%@: %p --- @{hash: %ld, name: %@, age: %ld}>",[self class], self, self.hash, self.name, self.age];
}
@end
Person *p1 = [[Person alloc] init];
p1.name = @"Tom";
p1.age = 3;
Person *p2 = [[Person alloc] init];
p2.name = @"Tom";
p2.age = 3;
NSMutableSet *s = [[NSMutableSet alloc] init];
[s addObject:p1];
[s addObject:p2];
NSLog(@"%@",s);
//{(
// <Person: 0x6000004bc720 --- @{hash: 105553121232672, name: Tom, age: 3}>,
// <Person: 0x6000004b86a0 --- @{hash: 105553121216160, name: Tom, age: 3}>
//)}
自定義對象Person，加入集合，從指針方面看，指向兩塊不同的內(nèi)存區(qū)域，從值方面看，集合中有兩個對象值相等的元素，不符合集合的互異性。因此就無法用該方法過濾重復(fù)元素了。
NSSet和NSDictionary在判斷成員是否相等時，會進行兩步判斷
（1）集合元素哈希值是否與目標哈希值相等，如果相等，進行下一步判斷，如果不相等，直接返回。
（2）在第一步成立的前提下，判斷對象等同性。
對象等同性
如果兩個對象內(nèi)存地址不一樣，但是其他的比如所包含的屬性值都一樣，那么對象也相等，可以稱為對象等同性。使用NSObject協(xié)議中聲明的“isEqual:”判定?！?=”是判斷指針是否相等，即是否指向同一內(nèi)存區(qū)域，得出的結(jié)果有時候未必是我們想要的。
NSObject協(xié)議中，有兩個用于判定等同性的關(guān)鍵方法
- (BOOL)isEqual:(id)object;
@property (readonly) NSUInteger hash;
這里需要了解兩點：
- NSObject類中，這兩個方法的默認實現(xiàn)是當(dāng)指針值相等時，這兩個對象相等。（像NSString等這些類，內(nèi)部重寫了“isEqual:”并擁有自己的例如“ isEqual ToString:”）
- 如果“isEuqal:”判定兩個對象相等，那兩個對象就有相同的hash值，但是如果兩個對象有相同的hash值，則“ isEqual:”未必認為兩對象相等。
因此，對自定義類Person進行比較
Person *p1 = [[Person alloc] init];
p1.name = @"Tom";
p1.age = 3;
Person *p2 = [[Person alloc] init];
p2.name = @"Tom";
p2.age = 3;
BOOL re1 = p1 == p2; //false
BOOL re2 = [p1 isEqual:p2]; //false
然é，我們通常認為，如果兩個對象的所有字段都相等，那兩個對象也相等。所以，我們重寫Person的“isEqual:”方法，同時可以實現(xiàn)屬于Person的“isEqualToPerson:”方法，相比于“isEqual:”方法，“isEqualToPerson:”更快，因為“isEqual:”不知道受測對象的類型，還要做額外的判斷。
-(BOOL)isEqual:(id)object
{
if (self == object) {
return YES;
}
if ([self class] != [object class]) {
return NO;
}
return [self isEqualToPerosn:object];
}
-(BOOL)isEqualToPerosn:(Person *)person
{
if (![_name isEqualToString:person.name]) {
return NO;
}
if (_age != person.age) {
return NO;
}
return YES;
}
/*
比較結(jié)果
*/
//<Person: 0x6000007d0fe0 --- @{hash: 105553124462560, name: Tom, age: 3}>
//<Person: 0x6000007d43c0 --- @{hash: 105553124475840, name: Tom, age: 3}>
再進行“isEqual:”比較，結(jié)果為true，但是卻沒有相同的hash值，這就要實現(xiàn)一下hash方法。
等同性約定：兩對象相等，hash值也相等，但是兩個hash值相等的對象未必相等。
hash方法的實現(xiàn)
- 方法一
-(NSUInteger)hash
{
return 1234;
}
??不推薦
容器（NSArray/NSDictionary/NSSet）在檢索哈希表時，會用對象的哈希碼做索引。哈希表本質(zhì)是數(shù)組，哈希表中每個元素可以看成是個箱子，每個箱子對應(yīng)一個哈希碼，相同的哈希碼放在同一個箱子中，同一個箱子中的元素以鏈表的形式存在，本例返回定值如果有很多的哈希碼都相等都在一個箱子中，那就相當(dāng)于遍歷了一遍，時間復(fù)雜度就變成了O(n)。而一般哈希表查找的時間復(fù)雜度為O(1)。
- 方法二
-(NSUInteger)hash
{
NSString *strToHash = [NSString stringWithFormat:@"%@:%ld",_name,(long)_age];
return [strToHash hash];
}
??不推薦
看似沒毛病，但是這樣做會負擔(dān)創(chuàng)建字符串的開銷。
- 方法三
-(NSUInteger)hash
{
return [_name hash] ^ _age;
}
??推薦
既能保持效率，又能減少相同哈希碼的碰撞。所以寫hash方法，要保證效率，同時一定程度內(nèi)減少碰撞，并且選擇對象中的重點字段進行計算即可。
/*
比較結(jié)果
“isEqual:” 為 TRUE
*/
//<Person: 0x60000397daa0 --- @{hash: 508504776, name: Tom, age: 3}>
//<Person: 0x600003972040 --- @{hash: 508504776, name: Tom, age: 3}>
用NSMutableSet對Person進行元素過濾的時，便可實現(xiàn)與NSString作為元素同樣的結(jié)果。
哈希表
理想狀態(tài)下不希望進行任何比較，一次存取就能得到所查記錄，這就需要在記錄的存儲位置和關(guān)鍵字之間建立關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中唯一的位置相對應(yīng)。假設(shè)給定關(guān)鍵字k值，則存儲位置在f(k)，f就是哈希函數(shù)。
既然是函數(shù)，就存在映射（關(guān)鍵字集合到地址集合），那也就關(guān)系到哈希表存取的性能問題，不同的關(guān)鍵字可能得到相同的哈希地址，即 k1 ≠ k2但 f(k1) = f(k2)。這種現(xiàn)象稱為沖突。
理想狀態(tài)下是一一映射，時間復(fù)雜度為O(1)，實際狀態(tài)下，難免存在沖突。
- 處理沖突的方法
1.開放定址法
2.再哈希法
3.鏈地址法
4.建立公共溢出區(qū)
處理沖突方法的效率存在差異，當(dāng)哈希表處理沖突方法相同，查找長度則依賴于哈希表的負載因子
負載因子 = 表中填入記錄數(shù) / 哈希表長度
因此，負載越小，發(fā)生沖突的可能性就越小。
推薦一篇關(guān)于哈希表的文章，寫的很好
??深入理解哈希表
總結(jié)
1.比較對象等同性，需要實現(xiàn)“isEqual:”和hash方法。
2.相同的對象要具有相同的哈希碼，但哈希碼相同的對象未必等同。
3.寫hash方法時，不用比較每一條屬性，挑幾個重點就行，為了保證效率的同時降低碰撞幾率。
