NSMutableDictionary 的内存布局

有关NSDictionary的内存布局，可以参看《NSDictionary 的内存布局》。
1 类图

和《NSDictionary 的内存布局》中的类图相比较，本章类图多了2个新成员:
__NSDictionaryM
__NSCFDictionary
2 __NSDictionaryM

通过下面的方式，可以创建__NSDictionaryM:

1. NSMutableDictionary *dictM = [NSMutableDictionary dictionary];NSMutableDictionary  *dict = [NSMutableDictionary dictionaryWithDictionary:@{"kaaa": @"aaa"}];

复制代码

从Xcode的控制台输出可以看到:

1. (lldb) po [dictM class]__NSDictionaryM

复制代码

2.1 初始化

__NSDictionaryM的初始化流程和__NSDictionaryI类似。
当调用+[NSMutableDictionary dictionaryWithDictionary:]方法时，最终会调用到-[__NSPlaceholderDictionary initWithObjects:forKeys:count]方法。
-[__NSPlaceholderDictionary initWithObjects:forKeys:count]方法在NSDictionary部分已经介绍过。
这里重新贴出与__NSDictionaryM相关的伪代码:

1. // -[__NSPlaceholderDictionary initWithObjects:forKeys:count]@interface __NSPlaceholderDictionary...@end@implementation __NSPlaceholderDictionary- (instancetype)initWithObjects:(ObjectType const[])objects forKeys:(ObjectTpye const[])keys count:(NSUInteger)count {  ...  label:  if (self == ___immutablePlaceholderDictionary) {    ...  } else if (self == ___mutablePlaceholderDictionary) {    // 创建 __NSDictionaryM    return __NSDictionaryM_new(keys, objecs, count, 3);  }    error "创建出错"}

复制代码

从伪代码可以看到，最终会调用到__NSDictionaryM_new方法。
下面就来看看__NSDictionaryM_new的内部实现。
和创建__NSDictionaryI对象一样，__NSDictionaryM_new一开始也需要遍历__NSDictionaryCapacities数组。
遍历的目的，同样是为了找到一个index，这个index对应的capacity大于或者等于count。

1. BOOL found = NO;NSInteger index = 0;for (; index < 40; index++) {  if (__NSDictionaryCapacity[i] >= count) {    found = YES;    break;  }}if (!found) {  error "不能创建 NSDictionary";}

复制代码

从上面伪代码可以看到，创建__NSDictionaryI最多遍历64项，而这里只遍历40项。
有了index，就可以从__NSDictionarySizes数组中，得到要创建的字典的size。

1. NSUInteger size = __NSDictionarySizes[index];

复制代码

有了要创建字典的size，接下来就要创建__NSDictionaryM对象:

1. __NSDictionaryM *dictM = __CFAllocateObject(__NSDictionaryM.class, 0);

复制代码

还记得创建__NSDictionaryI的代码吗?

1. __NSDictionaryI *dictI = __CFAllocateObject(__NSDictionaryM.class, size * 8 * 2);

复制代码

可以看到，在创建__NSDictionaryM对象时，并没有传入size信息。
这就是说，key-value对，不是保存在__NSDictionaryM本身中。
这个很好理解。
因为__NSDictionaryM可以动态的增加key-value对，而不像__NSDictionaryI一样，创建好之后就不能再变化了。
既然__NSDictionaryM的key-value对不存储在自身，那么肯定存在堆上的另外地方。
malloc_type_calloc方法正是用来分配这块内存的。
malloc_type_calloc的方法声明如下：

1. void *malloc_type_calloc(size_t num_items, size_t size malloc_type_id_t type_id);

复制代码

__NSDictionaryM_new内部调用malloc_type_calloc的方式为:

1. void *storage = malloc_type_calloc(1, size * 8 * 2, 0x8448092b);

复制代码

从代码可以看到，malloc_type_calloc创建了1个item，这个item的大小是size * 8 * 2。
毫无疑问，创建出来的storage正是用来存储key-value对的。
storage指针存储在__NSDictionaryM对象中，内存布局如下:

从上面的内存布局图可以看到，创建的存储区域分位2个数组。
key-value对中的key存储在第1个数组中。
key-value对中的value存储在第2个数组中。
为了存储key-value对，会遍历__NSDictionaryM_new函数的keys数组参数。
针对keys数组中的每一个key，计算其hash值。

1. for (NSInteger i = 0; i < count; i++) {  ObjectType key = keys[i];  NSUInteger hashValue = [key hash];}

复制代码

计算出hash值之后，对其进行取余计算，取余的结果作为storage.keys数组中的索引:

1. for (NSInteger i = 0; i < count; i++) {  ObjectType key = keys[i];  NSUInteger hashValue = [key hash];  NSInteger index = hashValue % size;}

复制代码

有了这个索引index，就可以读取storage.keys数组中的值:

1. for (NSInteger i = 0; i < count; i++) {  ObjectType key = keys[i];  NSUInteger hashValue = [key hash];  NSInteger index = hashValue % size;  ObjectType oldKey = storage.keys[index];}

复制代码

oldKey的值会有3种情形。
第1种情形，是oldKey的值为nil，说明这个位置之前没有值，可以放心将key-value对存入:

1. for (NSInteger i = 0; i < count; i++) {  ObjectType key = keys[i];  Objecttype value = values[i];  NSUInteger hashValue = [key hash];  NSInteger index = hashValue % size;  ObjectType oldKey = storage.keys[index];  if (oldKey == nil) {    storage.keys[index] = [key copyWithZone:nil];    storage.values[index] = value;  }}

复制代码

上面伪代码需要注意的时，存储key是，调用了copyWithZone:方法。
因此，要做字典的Key，必须遵循copy协议。
在__NSDictionaryM对象上，有25 bit记录存储的key-value对个数。
在这种情形下，这个值会加1。

第2种情形，是oldKey的值为___NSDictionaryM_DeletedMarker。
___NSDictionaryM_DeletedMarker是一个特殊的对象，它是一个NSObject：

1. 0x18052c7ac : add    x21, x21, #0x420 ; ___NSDictionaryM_DeletedMarker0x18052c7b0 : ldr    x8, [sp, #0x30]

复制代码

在Xcode的lldb控制台上输出:

1. (lldb) po $x21

复制代码

有关__NSDictionaryM_DeletedMarker在介绍removeObjectForKey:方法时会继续介绍。
此时，如果oldKey是一个__NSDictionaryM_DeletedMarker，那么就顺着storage.keys数组当前的位置往前继续查找，直到查找完storage.keys数组中的所有位置。
如果查找过程中找到了一个oldKey为nil的位置，那么就将key-value对放到这个位置。
同时，__NSDictionaryM对象中，记录存储key-value对个数的值加1。

如果遍历的过程中，找到了一个oldKey是一个普通对象，那么就是情形3了。
第3种情形，如果oldKey是一个普通的对象，那么就检测key和oldKey是否是同一个对象，或者它们的isEqual方法是否相等:

1. key == oldKey || [oldKey isEqual:key]

复制代码

如果它们是同一个对象，或者isEqual方法相等，那么将value直接覆盖oldKey对应的oldValue值。
注意，此时__NSDictionaryM对象中，记录存储key-value对个数的值不会有变化。

如果key和oldKey既不是同一个对象，它们的isEqual方法也不相等，那么就顺着当前storage.keys数组的位置往前找，直到遍历所有storage.keys数组的位置。
此时的情形和遇到__NSDictionaryM_DeletedMarker完全一样。
2.2 内存布局

cow是Copy On Write的缩写，再字典拷贝操作中有用，这里先不用关心。
2.3 objectForKey:

有了上面的内存布局，objectForKey:方法就很容易理解了。
首先根据参数key计算其hash值，并对hash值进行取余计算:

1. NSUInteger hashValue = [key hash];NSIndex index = hashValue % size;

复制代码

那size是从哪里获取的呢？
从上面内存布局图可以知道，__NSDictionaryM对象有6 bit记录size的索引。
有了这个索引，就可以轻松的从__NSDictionarySizes数组中获取到对应的size值了。
通过hash值计算出index后，将这个index作为storage.keys数组的索引，
读取一个值candidateKey。
此时也有3种情形。
情形1，如果candidateKey的值是nil，说明这个key在字典中没有对应的value，直接返回nil。
情形2，如果candidateKey是一个___NSDictionaryM_DeletedMarker对象，那么就从storage.keys数组的当前位置顺序向前找，直到遍历完所有storage.keys中的位置。
如果遍历的过程中，找到了一个candidateKey是nil，那么就直接返回nil。
如果遍历的过程中，找到了一个普通对象，那么就是情形3了。
情形3，如果candidateKey是一个普通对象，那么就检测它们是否是同一个对象，或者isEqual方法是否相等:

1. candidateKey == key || [candidateKey isEqual:key]

复制代码

如果满足上面的条件，就直接将candidateKey对应的value返回。
如果不满足上面的条件，那么就从storage.keys数组的当前位置顺序向前找，直到遍历完所有storage.keys中的位置。
如果遍历完所有位置，都没有找到合适的candidateKey，那么就返回nil。
2.4 setObject:forKey:

setObject:forKey方法首先根据参数key，计算其hash值。
根据hash值可以得到storage.keys数组中的索引，然后读取这个索引对应的值oldKey。
此时会有3种情形。
情形1，如果运气不错，oldKey为nil，那么说明这个位置没有被占用，直接将key-value对添加进去。
同时，__NSDictionaryM对象中记录存储key-value对个数的值会加1。

情形2，如果运气太差，oldKey是一个___NSDictionaryM_DeletedMarker，那么就从storage.keys数组的当前位置顺序向前找，直到遍历完所有storage.keys中的位置。
如果再查找的过程中，找到了一个没有被占用的位置，并不能直接将key-value对添加进去。
此时，需要判断查找的次数是否大于16次。
如果查找次数不大于16次，那么就直接添加key-value对:

如果大于16次，需要对整个storage数组进行重新哈希，避免频繁遇到___NSDictionaryM_DeletedMarker，造成频繁查找。
重新进行哈希，会创建新的storage数组，旧storage数组中的___NSDictionaryM_DeletedMarker不会存到新storage数组中。

从图中可以看到，重新哈希之后，新storage数组中的key-value对顺序，可能和旧storage数组中不一样。
重新哈希之后，需要重新计算参数key的hash值，重复上面的步骤。
如果查找过程中，oldKey是一个普通对象，那么就会遇到情形3。
情形3，如果oldKey是一个普通对象，那么就检测oldKey与key是否是同一个对象，或者它们的isEqual方法是否相等:

1. oldKey == key || [oldKey isEqual:key]

复制代码

如果满足条件，直接将oldKey对应的的值覆盖成参数value。
此时，__NSDictionaryM对象中记录存储key-value对的值不会变化。
如果不满足条件，也就是oldKey与参数key既不是同一个对象，它们的isEqual方法也不相等。
那么，就从storage.keys数组的当前位置顺序向前找，直到遍历完所有storage.keys中的位置。
整个流程和情形2完全一样。
需要注意的是，判断是否重新哈希的查找次数，是累计情形2和情形3的。
比如查找过程中遇到了一个___NSDictionaryM_DeletedMarker对象，那么查找计数加1。
紧接着查找，遇到了一个普通对象不满足:

1. oldKey == key || [oldKey isEqual:key]

复制代码

那么查找次数也要加1。
最后，如果遍历了当前storage.keys的所有位置，都没有找到合适的位置，那么将当前字典的size索引加1作为新的索引，从__NSDictionarySizes数组中得到一个新的size。
获取到新size之后，使用这个新size创建一个新的storage数组，然后将旧storage数组中的key-value对重新哈希到新storage数组中。
重新哈希之后，重头计算参数key的哈希值以及在新storage数组中的索引，重复上面步骤。

由于新storage数组发生了变化，根据参数key计算的索引值也可能会发生变化。
需要注意的是，只要set操作成功，就会触发根据__NSDictionaryM对象中的KVO标志，触发KVO:

1. [self willChangeValueForKey:key];// set key-value 对[self didChangeValueForKey:key];

复制代码

2.5 removeObjectForKey:

要进行删除操作，首先要看storage数组中，是否存在需要被删除的目标targetKey。
要成为targetKey，需要满足下面的条件:

1. targetKey == key || [targetKey isEqual:key]

复制代码

也就是说，目标targetKey要么和参数key是同一个对象，要么它们的isEqual方法相等。
要找到targetKey，会有一个查找过程。
查找过程和setObject:forKey:方法中的一样。
查找过程中也会记录查找的次数。
如果找到了targetKey，那么就使用___NSDictionaryM_DeletedMarker对象覆盖targetKey的值。
也就是说，___NSDictionaryM_DeletedMarker对象是删除操作产生的。
同时，需要将targetKey对应的value置nil。

但是，事情远远还没有结束。
删除完之后，还得看查找次数是否大于16次。
如果查找大于16次，需要将删除后的storage数组重新进行哈希操作。
重新哈希会产生新的storage数组，并且新的storage数组里面不会有___NSDictionaryM_DeletedMarker对象。
如果查找次数不超过16次，还需要检测被覆盖的targetKey所处位置的前一个位置的值。
如果前一个位置的值既不是一个___NSDictionaryM_DeletedMarker，也不是一个普通对象，而是nil，那么就会有一个清除___NSDictionaryM_DeletedMarker对象的操作。
清除过程从当前targetKey所处位置开始，向后遍历storage.keys数组，将碰到的___NSDictionaryM_DeletedMarker对象全部置成nil，直到遇到一个非___NSDictionaryM_DeletedMarker对象。
这个对象可以是nil，也可以是普通对象。

如果删除操作发生了，就会根据__NSDictionaryM对象中的KVO标志，触发KVO:

1. [self willChangeValueForKey:key];// 删除操作[self didChangeValueForKey:key];

复制代码

为什么删除的时候，需要一个___NSDictionaryM_DeletedMarker对象来进行占位呢？
因为有可能有2个key:key1和key2。
这2个key的hash值一样，但是isEqual方法不相等:

1. [key1 hash] == [key2 hash] && ![key1 isEqual:key2]

复制代码

那么根据前面的分析，这2个key都可以通过setObject:forKey:的方法添加到字典中。
如果此时删除key1，直接将它在storage.keys数组中的所在位置置成nil，那么当在key2上调用objectForKey:就会出问题。
因为key2和key1的hash值一样，计算出来的storage.keys数组索引也一样。
此时由于这个索引对应的值为nil，就会错误的返回nil给用户，而不是正确的值。
3 __NSCFDictionary

__NSCFDictionary字典是一个很奇怪的可变字典。
虽然它是可变的，但是如果使用不正确，就会造成崩溃。
通过下面的方式可以创建一个__NSCFDictionary字典:

1. // 创建一个可变字典    CFMutableDictionaryRef mutableDict = CFDictionaryCreateMutable(kCFAllocatorDefault, 0, NULL, NULL);

复制代码

通过Xcode的lldb控制台输出可以看到:

1. (lldb) po [mutableDict class]__NSCFDictionary(lldb) p (BOOL)[mutableDict isKindOfClass:NSMutableDictionary.class](BOOL) YES(lldb) p (BOOL)[mutableDict respondsToSelector:@selector(setObject:forKey:)](BOOL) YES

复制代码

从控制台的输出可以看到，__NSCFDictionary字典是一个可变字典。
同时，这个可变字典也有setObject:forKey:方法。
下面我们对这个字典进行copy操作:

1. NSDictionary *dict = [(__bridge NSMutableDictionary *)mutableDict copy];

复制代码

按照道理，调用copy方法之后，应该返回的是一个非可变字典，但是如果打印dict的类型，发现仍然是__NSCFDictionary:

1. (lldb) po [dict class]__NSCFDictionary

复制代码

如果我们使用isKindOfClass:方法对其进行判断，然后强转成NSMutableDictionary执行setObject:forKey:方法，就会发生崩溃:

1. if ([dict isKindOfClass:NSMutableDictionary.class]) {      [(NSMutableDictionary *)dict setObject:@"hh" forKey:@"cc"];}

复制代码

崩溃信息为:

1. Thread 1: "-[__NSCFDictionary setObject:forKey:]: mutating method sent to immutable object"

复制代码

为了搞清楚原因，我们首先得从CFDictionaryCreateMutable函数入手。
CFDictionaryCreateMutable函数的汇编代码如下:

1. CoreFoundation`CFDictionaryCreateMutable:    ...    // 1. 调用 __NSCFDictionaryCreateMutable 方法    0x1803d53c4 :  bl     0x180529394               ; __NSCFDictionaryCreateMutable    0x1803d53c8 :  mov    x19, x0    0x1803d53cc :  cbnz   x0, 0x1803d5430           ;     ...    // 2. 调用 __CFDictionaryCreateGeneric    0x1803d53dc :  bl     0x1803d52e8               ; __CFDictionaryCreateGeneric  ...  // 3. 设置 isa 为 __NSCFDictionary  0x1803d540c : bl     0x18041e80c               ; _CFRuntimeSetInstanceTypeIDAndIsa

复制代码

从汇编代码可以知道，CFDictionaryCreateMutable内部会调用2个函数创建字典。
首先调用__NSCFDictionaryCreateMutable方法，调用的方式为:

1. __NSCFDictionaryCreateMutable(kCFAllocatorDefault, 0, NULL, NULL);

复制代码

这个方法的汇编代码如下:

1. CoreFoundation`__NSCFDictionaryCreateMutable:    ...    // 1. 检测第 3 个参数    0x180529418 : add    x8, x8, #0x948            ; kCFTypeDictionaryValueCallBacks    0x18052941c : cmp    x21, x9    0x180529420 : b.ne   0x180529434               ;     ...    // 2. 检测第 4 个参数    0x180529434 : adrp   x9, 407675    0x180529438 : add    x9, x9, #0x918            ; kCFCopyStringDictionaryKeyCallBacks    ...    // 3. 熟悉的 __NSDictionaryM_new 方法    0x18052946c : b      0x18052c694               ; __NSDictionaryM_new    // 4. 返回 nil    0x180529470 : mov    x0, #0x0                  ; =0     0x180529474 : ldp    x29, x30, [sp, #0x30]    0x180529478 : ldp    x20, x19, [sp, #0x20]    0x18052947c : ldp    x22, x21, [sp, #0x10]    0x180529480 : ldp    x24, x23, [sp], #0x40    0x180529484 : ret       ...

复制代码

由于调用__NSCFDictionaryCreateMutable时，第3个参数和第4个参数传的都是NULL，因此程序直接跳转到代码注释4处执行。
也就是跳过了我们熟悉的__NSDictionaryM_new方法，失去了创建OC可变字典的机会，直接返回nil。
由于__NSCFDictionaryCreateMutable方法返回nil，__CFDictionaryCreateGeneric方法得到执行。
__CFDictionaryGeneric方法的汇编代码如下:

1. CoreFoundation`__CFDictionaryCreateGeneric:    ...    // 1. 调用 CFBasicHashCreate 方法    0x1803d5374 : bl     0x1804ebe30               ; CFBasicHashCreate

复制代码

可以看到__CFDictionaryGeneric方法直接调用了CFBasicHashCreate方法。
这个方法会创建一个CFBasichash对象，是一个CF类型:

1. (lldb) po $x0{type = mutable dict, count = 0,entries =>}

复制代码

创建完毕之后，CFDictionaryCreateMutable方法在代码注释3处调用了_CFRuntimeSetInstanceTypeIDAndIsa方法。
_CFRuntimeSetInstanceTypeIDAndIsa方法将CFBasicHash的isa设置成__NSCFDictionary。
这样这个CF对象就能桥接成OC对象了，但它本质上还是一个CF对象。
3.1 copy

那为什么调用copy方法，返回的字典还是一个可变的呢？
原因是__NSCFDictionary重写了copyWithZone:方法。
__NSCFDictionary的copyWithZone:方法汇编代码如下:

1. CoreFoundation`-[__NSCFDictionary copyWithZone:]:    // 1. 检测当前对象是不是 OC 里面的可变字典    0x1803e3d14 :  bl     0x1803d5e88               ; _CFDictionaryIsMutable    0x1803e3d18 :  cbz    w0, 0x1803e3d30           ;     ...    // 2. 调用 CFDictionaryCreateCopy    0x1803e3d2c :  b      0x1803d5448               ; CFDictionaryCreateCopy

复制代码

代码注释1，检测当前对象是否是一个OC的可变字典。
很明显，当前对象是一个CF对象，只是能桥接为OC对象，因此检测不成立。
代码注释2，调用CFDictionaryCreateCopy方法进行拷贝。
这个方法拷贝出来的仍是一个__NSCFDictionary对象，其汇编代码如下:

1. CoreFoundation`CFDictionaryCreateCopy:    ...    // 1. 拷贝当前对象    0x1803d5484 :  bl     0x1804ec1b8               ; CFBasicHashCreateCopy    ...    0x1803d54b0 : mov    x0, x19    0x1803d54b4 : mov    w1, #0x12                 ; =18     // 2. 设置拷贝出来的对象的 isa 为 __NSCFDictionary    0x1803d54b8 : bl     0x18041e80c               ; _CFRuntimeSetInstanceTypeIDAndIsa

复制代码

3.3 setObject:forKey:

那为什么强转成可变字典，调用setObject:forKey:方法会发生崩溃呢？
下面就来看下setObject:forKey:方法的汇编代码:

1. CoreFoundation`-[__NSCFDictionary setObject:forKey:]:     ...    // 1. 检测当前对象是否是 OC 的可变字典    0x1803e3968 :  bl     0x1803d5e88               ; _CFDictionaryIsMutable    0x1803e396c :  tbz    w0, #0x0, 0x1803e39ec     ;     ...    0x1803e39ec : mov    x0, x19    0x1803e39f0 : mov    x1, x21    // 2. 检测失败会执行到这里    0x1803e39f4 : bl     0x18053d8ac               ; -[__NSCFDictionary setObject:forKey:].cold.1    ...

复制代码

代码注释1，检测当前对象是否是OC的可变字典。
很明显，当前对象是一个CF类型，不是一个OC对象，检测失败。
代码注释2，检测失败后，会指向到这里。
-[__NSCFDictionary setObject:forKey:].cold.1看名字就知道不简单。
它的汇编代码如下:

1. CoreFoundation`-[__NSCFDictionary setObject:forKey:].cold.1:    ...    0x18053d8c0 : add    x8, x8, #0xeb8            ; NSInternalInconsistencyException    ...    0x18053d8d4 : add    x1, x1, #0x700            ; @"%@: mutating method sent to immutable object"    ...

复制代码

从代码上看，正是这个函数抛出了异常。
3.4 isKindOfClass:

__NSCFDictionary字典虽然是一个可变字典，通过了isKindOfClass:方法检测，但是确不能强转着使用。
苹果文档中，关于isKindOfClass:对类簇的讨论，到这里，才变得十分具体:

Be careful when using this method on objects represented by a class cluster. Because of the nature of class clusters, the object you get back may not always be the type you expected. If you call a method that returns a class cluster, the exact type returned by the method is the best indicator of what you can do with that object

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！