你所需要了解的 NSDictionary
in 技术 with 0 comment

你所需要了解的 NSDictionary

in 技术 with 0 comment

前言

在上正文之前,我们来看看为什么需要阅读这篇文章,或者是为什么吸引我来研究它?

局限性

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 中也可以重现。

复制

接下来讲讲复制...
未完,待续。

Responses