前言
在上正文之前,我们来看看为什么需要阅读这篇文章,或者是为什么吸引我来研究它?
局限性
NSDictionary
提供了 {key : value} 的映射。从本质上讲,NSDictionary
中存储的 value 位置是由 key 来索引的。由于对象存储在特定位置,NSDictionary
中要求 key 的值不能改变(否则 value 的位置会错误)。为了保证这一点,NSDictionary
会始终复制 key 到自己私有空间。
这个 key 的复制行为也是 NSDictionary
如何工作的基础,但这也有一个限制:你只能使用 OC 对象作为 NSDictionary
的 key,并且必须支持 NSCopying 协议。此外,key 应该是小且高效的,以至于复制的时候不会对 CPU 和内存造成负担。
这意味着,NSDictionary
中真的只适合将值类型的对象作为 key(如简短字符串和数字)。并不适合自己的自定义类来做对象到对象的映射。
声明
上面那段话看不太明白也没关系,接下来会慢慢给你解析其中的关键点。首先需要声明的是这篇文章的重点是 NSDictionary
,并不是为了解决上面问题而教你怎么使用 NSMapTable
。
isEqual:
Key 是 NSDictionary
如何工作的基础,那跟 isEqual:
有什么关系呢?
NSMutableDictionary *dic = [NSMutableDictionary dictionary];
dic[@"a"] = @"1";
dic[@"a"] = @"2";
上面的代码的结果我们都知道是 {"a":"2"}
,因为后面会覆盖前面的。如何判定是否覆盖或新增?这就是 isEqual:
的作用。
如果是自定义对象作为 Key 呢?下面是我们通常做覆盖的标准方法:
///MARK: - Equal
- (BOOL)isEqual:(id)other{
if (other == self) {
return YES;
} else if (![other isKindOfClass:self.class]) {
return NO;
} else {
return [self isEqualToObject:other];
}
}
- (BOOL)isEqualToObject:(TestBaseObject *)other{
if (other == nil) {
return NO;
}
BOOL equalName = (self.name != nil && other.name != nil && [self.name isEqualToString:other.name]);
BOOL equalAge = (self.age != nil && other.age != nil && [self.age isEqualToNumber:other.age]);
BOOL equalHeight = self.height == other.height;
return equalName && equalAge && equalHeight;
}
从上面可以看出来,如果是字符串 a 作为 key,在第一步的 if 判断内存地址的时候,就能决定它们是否覆盖,比起自定义对象的判定步骤要少得多。
因为系统在编译期对 NSString 有内存优化,存放在常量区,所以它们内存地址会相同。NSNumber 同理,也会有相同效果。
如果自定义对象作为 NSDictionary
的 key,在不重写 isEqual:
方法的情况下会怎么样呢?
TestBaseObject *obj = [[TestBaseObject alloc] initWithName:@"wahaha" age:@(1) hegiht:200];
NSMutableDictionary *mDic = [NSMutableDictionary dictionary];
[mDic setObject:@"1" forKey:obj];
id value = mDic[obj];
上面 value 的值是 nil,因为 isEqual:
默认比较的是内存地址。而 TestBaseObject
实现了 NSCopying
协议,在 forKey: 的时候会做拷贝处理,拷贝后的 obj 跟原来的 obj 内存地址肯定不一样。除非迭代,否则再也无法获取到对应的 Object 值。
hash
Key 是 NSDictionary
如何工作的基础,那跟 hash
有什么关系呢?
由于 NSDictionary
中的 key-value 是无序的,因为它是散列结构。它没有像 NSArray
一样是有序的,因为 NSArray
是连续结构。 前者 dic[@"1"] 有值,并不能代表 dic[@"0"] 一定有值,后者 array[1] 有值就一定代表 array[0] 有值。
如果在没有 hash 的情况下,通过 key 查找对应的 value,时间复杂度为 O(n),n 为字典的长度(count)。而 hash 就像数组的下标,在理想情况下,时间复杂度甚至降低为O(1)。
所以,hash 的目的是为了提高通过 Key 在查找 Value 时候的效率。
hash 的默认实现是内存地址的十进制格式:
- (NSUInteger)hash{
NSUInteger hash = (NSUInteger)self;
return hash;
}
同样的,既然有默认实现,为什么还需要自己覆盖 hash 方法呢?
for (NSUInteger index = 0; index< 20; index ++) {
TestBaseObject *obj1 = [[TestBaseObject alloc] initWithName:@"wahaha" age:@(1) hegiht:200];
TestBaseObject *obj2 = [[TestBaseObject alloc] initWithName:@"wahaha" age:@(1) hegiht:200];
NSMutableDictionary *mDic = [NSMutableDictionary dictionary];
[mDic setObject:@"1" forKey:obj1];
[mDic setObject:@"2" forKey:obj2];
NSLog(@"count:%zi", mDic.count);
}
输出结果:
call super isEqual: method
count:1
call super isEqual: method
count:1
count:2
count:2
count:2
.....
TestBaseObject 是一个继承自 NSObject 的子类,根据上面的标准方法重写了 isEqual:
方法,但是没有重写 hash
方法。其中循环执行是为了让情况更加容易重现,根据日志你能发现 NSDictionary
的长度变得很不稳定。
关于这个问题网上很多文章的想法都是:
当前对象的 hash 值是否和目标对象 hash 值相等,如果相等则继续进行 isEqual 判定,如果不相等则直接判定为不相等。
实际结果是 hash
不相等,却依旧进行 isEqual:
的判定。它并不像是一个纯函数,实际情况也比网上说的要复杂得多。最终能找到的比较合理的解释是:
isEqual 的调用猜测应该是根据系统底层哈希表的实现来的。并不只是简单的根据 hash 值来决定。
纯函数:此函数在相同的输入值时,需产生相同的输出。
为了消除这种不稳定性,我们需要覆盖 hash
方法。并且在 isEqual: 相等的时候,必须要具有相同的 hash 值。下面是苹果官方的一段方法注释:
If two objects are equal (as determined by the isEqual: method), they must have the same hash value. This last point is particularly important if you define hash in a subclass and intend to put instances of that subclass into a collection.
如果两个对象相等(由isEqual:方法判定),则它们必须具有相同的哈希值。如果您在子类中定义哈希并将打算将该子类的实例放入集合中,则最后一点特别重要。
目前我们发现在集合 NSDictionary 和 NSSet 中会用到 hash 值。所以上面示例中的不稳定的问题,在 NSSet 中也可以重现。
复制
接下来讲讲复制...
未完,待续。
本文由 Bill 创作。
最后编辑时间为: 2020.07.13 at 02:54 pm