问题引入
用集合过滤重复元素
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，加入集合，从指针方面看，指向两块不同的内存区域，从值方面看，集合中有两个对象值相等的元素，不符合集合的互异性。因此就无法用该方法过滤重复元素了。
NSSet和NSDictionary在判断成员是否相等时，会进行两步判断
（1）集合元素哈希值是否与目标哈希值相等，如果相等，进行下一步判断，如果不相等，直接返回。
（2）在第一步成立的前提下，判断对象等同性。
对象等同性
如果两个对象内存地址不一样，但是其他的比如所包含的属性值都一样，那么对象也相等，可以称为对象等同性。使用NSObject协议中声明的“isEqual:”判定。“==”是判断指针是否相等，即是否指向同一内存区域，得出的结果有时候未必是我们想要的。
NSObject协议中，有两个用于判定等同性的关键方法
- (BOOL)isEqual:(id)object;
@property (readonly) NSUInteger hash;
这里需要了解两点：
- NSObject类中，这两个方法的默认实现是当指针值相等时，这两个对象相等。（像NSString等这些类，内部重写了“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:”方法，同时可以实现属于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;
}
/*
比较结果
*/
//<Person: 0x6000007d0fe0 --- @{hash: 105553124462560, name: Tom, age: 3}>
//<Person: 0x6000007d43c0 --- @{hash: 105553124475840, name: Tom, age: 3}>
再进行“isEqual:”比较，结果为true，但是却没有相同的hash值，这就要实现一下hash方法。
等同性约定：两对象相等，hash值也相等，但是两个hash值相等的对象未必相等。
hash方法的实现
- 方法一
-(NSUInteger)hash
{
return 1234;
}
🌚不推荐
容器（NSArray/NSDictionary/NSSet）在检索哈希表时，会用对象的哈希码做索引。哈希表本质是数组，哈希表中每个元素可以看成是个箱子，每个箱子对应一个哈希码，相同的哈希码放在同一个箱子中，同一个箱子中的元素以链表的形式存在，本例返回定值如果有很多的哈希码都相等都在一个箱子中，那就相当于遍历了一遍，时间复杂度就变成了O(n)。而一般哈希表查找的时间复杂度为O(1)。
- 方法二
-(NSUInteger)hash
{
NSString *strToHash = [NSString stringWithFormat:@"%@:%ld",_name,(long)_age];
return [strToHash hash];
}
🌚不推荐
看似没毛病，但是这样做会负担创建字符串的开销。
- 方法三
-(NSUInteger)hash
{
return [_name hash] ^ _age;
}
🌝推荐
既能保持效率，又能减少相同哈希码的碰撞。所以写hash方法，要保证效率，同时一定程度内减少碰撞，并且选择对象中的重点字段进行计算即可。
/*
比较结果
“isEqual:” 为 TRUE
*/
//<Person: 0x60000397daa0 --- @{hash: 508504776, name: Tom, age: 3}>
//<Person: 0x600003972040 --- @{hash: 508504776, name: Tom, age: 3}>
用NSMutableSet对Person进行元素过滤的时，便可实现与NSString作为元素同样的结果。
哈希表
理想状态下不希望进行任何比较，一次存取就能得到所查记录，这就需要在记录的存储位置和关键字之间建立关系f，使每个关键字和结构中唯一的位置相对应。假设给定关键字k值，则存储位置在f(k)，f就是哈希函数。
既然是函数，就存在映射（关键字集合到地址集合），那也就关系到哈希表存取的性能问题，不同的关键字可能得到相同的哈希地址，即 k1 ≠ k2但 f(k1) = f(k2)。这种现象称为冲突。
理想状态下是一一映射，时间复杂度为O(1)，实际状态下，难免存在冲突。
- 处理冲突的方法
1.开放定址法
2.再哈希法
3.链地址法
4.建立公共溢出区
处理冲突方法的效率存在差异，当哈希表处理冲突方法相同，查找长度则依赖于哈希表的负载因子
负载因子 = 表中填入记录数 / 哈希表长度
因此，负载越小，发生冲突的可能性就越小。
推荐一篇关于哈希表的文章，写的很好
👉深入理解哈希表
总结
1.比较对象等同性，需要实现“isEqual:”和hash方法。
2.相同的对象要具有相同的哈希码，但哈希码相同的对象未必等同。
3.写hash方法时，不用比较每一条属性，挑几个重点就行，为了保证效率的同时降低碰撞几率。
