NSDictionary 内存布局

NSDictionary是iOS开发中经常用到的数据结构。
熟悉NSDictionary的内部实现，有助于我们更好的使用它们。
同时，在遇到相关崩溃，也能帮助我们更好的分析问题。
1 类簇

非可变字典由NSDictionary表示。
可变字典由NSMutableDictionary表示。
按照苹果官方文档的说法，NSDictionary和NSMutableDictionary都是类簇。
也就是说，NSDictionary和NSMutableDictionary只是暴露的公共接口，具体实现由内部众多私有子类完成。

2 类图

3 NSDictionary

下面介绍各个非可变字典的内存布局。
3.1 __NSDictionary0

__NSDictioanry0里面没有任何元素。

1. NSDictionary *dict = @{};
3. NSDictionary *dict = [NSdictionary dictionary];

复制代码

上面代码都会创建一个__NSDictionary0。

1. (lldb) p dict
2. (__NSDictionary0 *) 0x00000001e3dd2390 0 key/value pairs

复制代码

3.2 NSConstantDictionary

如果字典初始化时key-value对都是字符串常量，那么就会得到一个NSConstantDictionary。

1. NSDictionary *dict = @{
2.   @"kaaa": @"aaa",
3.   @"kbbb": @"bbb",
4.   @"kccc": @"ccc",
5.   @"kddd": @"ddd",
6. };

复制代码

上面代码会创建一个NSConstantDictionary。

1. (lldb) p dict
2. (NSConstantDictionary *) 0x00000001021b87c8 4 key/value pairs

复制代码

如果key不全是字符串，也不会得到NSConstantDictionary:

1. NSDictionary *dict = @{
2.         @1: @"aaa",
3.         @2: @"bbb",
4.         @3: @"ccc",
5.         @4: @"ddd",
6.     };

复制代码

上面代码会得到一个__NSDictionaryI:

1. (lldb) p dict
2. (__NSDictionaryI *) 0x0000600002c0af80 4 key/value pairs

复制代码

3.2.1 内存布局

NSConstantDictionary的内存布局如下图所示:

isa指向对应的类对象。
options在调试时只遇到过值为1的情形，表示字典的key全是字符串。
当调用-[NSDictionary objectForKey:]方法时，如果参数不是字符串，不会处理:

1.   -[NSConstantDictionary objectForKey:]:
2.   ...
3.   // 1. x21 中存储方法参数
4.   0x180430b60 <+120>: mov    x0, x21
5.   // 2. w23 存储的计时 options 的值
6.   0x180430b64 <+124>: tbnz   w23, #0x1, 0x180430b8c    ; <+164>
7.   // 3. 判断参数是否是字符串
8.   0x180430b68 <+128>: bl     0x1804cf7ac               ; _NSIsNSString
9.   ...

复制代码

代码注释1，寄存器x21存储方法参数，传递给寄存器x0，作为下面函数_NSIsNSString的参数。
代码注释2，寄存器w23存储options的值，options为1，才会调用下面的函数_NSIsNSString方法。
代码注释3，调用_NSIsNSString方法对参数进行校验。
count存储字典中key-value的个数
keys是一个指针，指向字典中key所在的数组。
values是一个指针，指向字典中value所在的数组。
3.2.2 objectForKey:

使用objectForKey:方法读取一个key对应的value时:
1 使用二分法从keys数组中找到对应key所在的索引；
2 从values数组中根据索引返回对应的value值。

1.   -[NSConstantDictionary objectForKey:]:
2.   ...
3.   // 1. 调用二分法寻找参数在 keys 数组中的地址
4.   0x180430c58 <+368>: bl     0x180547f18               ; symbol stub for: bsearch
5.   0x180430c5c <+372>: cbz    x0, 0x180430c6c           ; <+388>
6.   // 2. 计算参数在 keys 数组中的索引
7.   0x180430c60 <+376>: sub    x8, x0, x19
8.   // 3. 获取 value 在 values 数组中地址
9.   0x180430c64 <+380>: add    x22, x22, x8
10.   // 4. 获取 value 值
11.   0x180430c68 <+384>: ldr    x0, [x22]
12.   ...

复制代码

代码注释1，调用二分法bsearch获取参数key在keys数组中所在地址，存储到x0。
代码注释2，x19指向keys数组首地址，这里计算出参数key在keys数组中的偏移量，也就是对应索引。
代码注释3，x22指向values数组首地址，这里计算出value在values数组中的地址。
代码注释4，从values数组中加载出value值，存储到x0。

3.3 __NSSingleEntryDictionaryI

如果字典中只有一个key-value对，就会得到__NSSingleEntryDictionaryI。

1. NSDictionary *dict = @{
2.         @5: @"555",
3. };

复制代码

上面代码会创建一个__NSSingleEntryDictionaryI:

1. (lldb) p dict
2. (__NSDictionaryI *) 0x0000600002c0af80 4 key/value pairs

复制代码

但是，如果key是字符串，得到的还是NSConstantDictionary:

1. NSDictionary *dict = @{
2.         @"5": @"555",
3. };

复制代码

上面代码会创建一个NSConstantDictionary:

1. (lldb) p dict
2. (NSConstantDictionary *) 0x000000010445c7d8 1 key/value pair

复制代码

3.3.1 内存布局

__NSSingleEntryDictionaryI的内存局部如下:

isa指向对应类对象。
key是一个指针，指向对应的key值
value是一个指针，指向对应的value值。
3.3.2 objectForKey:

__NSSingleEntryDictionaryI调用objectForKey:比较简单:
1 比较参数是否和存储的key值相等；
2 如果相等，就将存储的value返回。
3.4 __NSDictionaryI

大多数情况下，创建的NSDictionary对象，对应的类都是__NSDictionaryI。
3.4.1 初始化

通常我们会使用下面的函数初始化一个NSDictionary对象:

1. NSDictionary *dict = @{
2.     @"kaaa": @"aaa",
3.     @"kbbb": @"bbb",
4.     @"kccc": @"ccc",
5.     @"kddd": @"ddd",
6. };
8. NSDictionary *dictI = [NSDictionary dictionaryWithDictionary:dict];

复制代码

上面函数会创建一个__NSDictionaryI对象:

1. (lldb) p dictI
2. (__NSDictionaryI *) 0x0000600002c07f80 4 key/value pairs

复制代码

下面我们来看一下+[NSDictionary dictionaryWithDictionary:]方法的初始化过程。

1. CoreFoundation`+[NSDictionary dictionaryWithDictionary:]:
2. ->  ...
3.     0x1804b81a4 <+12>: mov    x19, x2
4.     // 1. 调用 objc_alloc 方法
5.     0x1804b81a8 <+16>: bl     0x1805488cc               ; symbol stub for: objc_alloc
6.     0x1804b81ac <+20>: mov    x2, x19
7.     0x1804b81b0 <+24>: mov    w3, #0x0                  ; =0
8.     // 2. 调用 initWithDictionary:copyItems: 方法
9.     0x1804b81b4 <+28>: bl     0x180757aa0               ; objc_msgSend$initWithDictionary:copyItems:
10.     ...

复制代码

代码注释1，调用objc_alloc为一个NSDictionary对象的内存空间。
代码注释2，调用initWithDictionary:copyItems:方法初始化第1步分配的内存空间。
但是当断点到initWithDictionary:copyItems:方法时，发现调用的是-[__NSPlaceholderDictionary initWithDictionary:compyItems:]方法，而不是期望的-[__NSDictionaryI initWithDictionary:copyItems:]方法。

1. CoreFoundation`-[__NSPlaceholderDictionary initWithDictionary:copyItems:]:
2. ->  0x180528b2c <+0>:   sub    sp, sp, #0x60
3.     0x180528b30 <+4>:   stp    x24, x23, [sp, #0x20]
4.     0x180528b34 <+8>:   stp    x22, x21, [sp, #0x30]
5.     0x180528b38 <+12>:  stp    x20, x19, [sp, #0x40]
6.     0x180528b3c <+16>:  stp    x29, x30, [sp, #0x50]

复制代码

那就说明，方法objc_alloc分配了一个__NSPlaceholderDictionary对象。
从上面的类图可以知道，__NSPlaceholderDictionary继承自NSMutableDictionary。
非可变字典从可变字典初始化而来，出乎意料之外。
下面就来看下objc_alloc的实现。
objc_alloc函数源码位于objc4中的NSObject.mm文件中。
但是我们还是从汇编角度来看一下它的实现。

1. libobjc.A.dylib`objc_alloc:
2.     ...
3.     // 1. 获取 isa 指针
4.     0x1800917dc <+4>:  ldr    x8, [x0]
5.     // 2. 掩码运算，剔除 isa 指针中的多余值
6.     0x1800917e0 <+8>:  and    x8, x8, #0x7ffffffffffff8
7.     // 3. 加载 AWZ 标志位
8.     0x1800917e4 <+12>: ldrh   w8, [x8, #0x1e]
9.     // 4. 判断是否没有设置 AWZ 标志
10.     0x1800917e8 <+16>: tbz    w8, #0xe, 0x1800917f4     ; <+28>
11.     // 5. 有 AWZ 标志位，就跳转执行 _objc_rootAllocWithZone 函数
12.     0x1800917ec <+20>: b      0x180086eec               ; _objc_rootAllocWithZone
13.     0x1800917f0 <+24>: ret   
14.     0x1800917f4 <+28>: adrp   x8, 482527
15.     // 6. 如果没有设置了 AWZ 标志，执行 allocWithZone: 方法
16.     0x1800917f8 <+32>: add    x1, x8, #0x6e0
17.     0x1800917fc <+36>: b      0x18006b400               ; objc_msgSend

复制代码

代码注释1，获取isa指针。
由于我们调用objc_alloc传入的是NSDictionary.class对象，所以这里的isa指针指向NSDictionary.class的元类。

代码注释2，对isa指针做掩码运算，剔除不相干的位。
众所周知，iOS中的isa并不是所有的bit都是类对象指针，有些bit用作了其他用处。
iOS 12又引入了PAC指针验证机制，isa各个bit的使用有了变化。
下面是objc4源码中，对isa指针的最新定义:

1. // isa.h
2. ...
3. #   elif __has_feature(ptrauth_calls) || TARGET_OS_SIMULATOR
4. #     define ISA_MASK        0x007ffffffffffff8ULL
5. #     define ISA_MAGIC_MASK  0x0000000000000001ULL
6. #     define ISA_MAGIC_VALUE 0x0000000000000001ULL
7. #     define ISA_HAS_CXX_DTOR_BIT 0
8. #     define ISA_BITFIELD                                          
9.         uintptr_t nonpointer        : 1;  // 此标志为 1，表明 isa 指针并不是纯粹的类指针                           
10.         uintptr_t has_assoc         : 1;  // 是否有关联对象            
11.         uintptr_t weakly_referenced : 1;  // 是否有弱引用            
12.         uintptr_t shiftcls_and_sig  : 52;  // 真正的类指针            
13.         uintptr_t has_sidetable_rc  : 1;  // 是否启用了 sidetable 来引用计数                  
14.         uintptr_t extra_rc          : 8 // 优先使用 8 bit 进行引用计数

复制代码

从定义中可以看到，isa指针中，只有52bit用于真正的类指针。
因此，isa指针的掩码为0x7ffffffffffff8，刚好52个1。
代码注释3，加载NSDictionary的元类中的AWZ标志。
AWZ就是AllocWithZone的简写。
如果设置了AWZ标志，就说明这个类用默认的alloc或者allocWithZone:方法。
如果不设置AWZ标志，那就说明这个类对于alloc或者allocWithZone:方法有自己的实现。
我们可以看到在objc4源码中有对应的注释:

1. // objc-runtime-new.h
2. // class or superclass has default alloc/allocWithZone: implementation
3. // Note this is is stored in the metaclass.
4. #   define FAST_CACHE_HAS_DEFAULT_AWZ    (1<<14)

复制代码

打印返回的对象:

1. (lldb) po (char *)$x1
2. "alloc"

复制代码

顺便看一下__NSDictionaryMutablePlaceholder方法:

1. CoreFoundation`+[NSDictionary allocWithZone:]:
2.     ...
3.     0x1804b6d04 <+28>:  adrp   x8, 407836
4.     0x1804b6d08 <+32>:  ldr    x8, [x8, #0x600]
5.     // 1. 比较当前类对象是否是 NSDictionary
6. ->  0x1804b6d0c <+36>:  cmp    x8, x0
7.     0x1804b6d10 <+40>:  b.eq   0x1804b6d64               ; <+124>
8.     0x1804b6d14 <+44>:  adrp   x8, 407836
9.     0x1804b6d18 <+48>:  ldr    x8, [x8, #0x608]
10.     // 2. 比较当前类对象是否是 NSMutableDictionary
11.     0x1804b6d1c <+52>:  cmp    x8, x0
12.     0x1804b6d20 <+56>:  b.eq   0x1804b6d88               ; <+160>
13.     ...
14.     // 3. 当前类是 NSDictionary，将执行 __NSDictionaryImmutablePlaceholder 方法
15.     0x1804b6d84 <+156>: b      0x180528728               ; __NSDictionaryImmutablePlaceholder
16.     ...
17.     // 4. 当前类是 NSMutableDictionary，将执行 __NSDictionaryMutablePlaceholder 方法
18.     0x1804b6da8 <+192>: b      0x180528734               ; __NSDictionaryMutablePlaceholder

复制代码

方法也很简单，也是直接返回一个__NSPlaceholderDictionary对象:

1. (lldb) po (char *)$x1
2. "alloc"

复制代码

__NSPlaceholderDictionary对象的创建流程我们已经清楚了。
接下来，继续看-[__NSPlaceholderDictionary initWithDictionary:copyItems:]方法。
汇编代码不看了，直接上伪代码:

1. (lldb) po [$x0 class]
2. __NSPlaceholderDictionary

复制代码

__NSDictionaryM和__NSFrozenDictionaryM在介绍可变字典时会涉及。
字典的拷贝在介绍完可变与非可变字典后会涉及。
由于本次例子中，我们使用的是一个NSConstantDictionary进行初始化，因此会调用到-[super initWithDictionary:copyItems:]方法。
__NSPlaceholderDictionary的super中，NSDictionary实现了这个方法。
-[NSDictionary initWithDictionary:copyItems:]不看汇编了，伪代码如下:

1. CoreFoundation`__NSDictionaryMutablePlaceholder:
2.     0x180528734 <+0>: adrp   x0, 407690
3.     0x180528738 <+4>: add    x0, x0, #0x348            ; ___mutablePlaceholderDictionary
4. ->  0x18052873c <+8>: ret

复制代码

如果遍历了全部的64想，仍然没有满足条件的索引，那么程序就会crash。
需要注意的是，__NSDictionaryCapacity中存储的capacity，并不是要创建的字典的大小。
要创建的字典的大小，存储在全局变量__NSDictionarySizes中:

1. (lldb) po [$x0 class]
2. __NSPlaceholderDictionary

复制代码

在Xcode的lldb中查看其内容为:

1. @interface __NSPlaceholderDictionary
2. ...
3. @end
5. @implementation
7. - (instancetype)initWithDictionary:(NSDictionary *)dict copyItems:(BOOL)shouldCopy {
8.   if (dict.class != __NSDictionaryI.class && dict.class != __NSDictionaryM.class && dict.class != __NSFrozenDictionaryM.class) {
9.   return [super initWithDictionary:dict copyItems:shouldCopy];
10.   }
11.   
12.   if (self == ___mutablePlaceholderDictionary) {
13.     return [dict mutableCopyWithZone:0];
14.   }
15.   
16.   if (self == ___immutablePlaceholderDictionary) {
17.     return [dict copyWithZone:0];
18.   }
19.   
20. }
21. @end

复制代码

从输出可以看到，除了第0项和第1项之外，其他各项的值与__NSDictionaryCapacity中的值都不相等。
通过上面遍历__NSDictionaryCapacity数组查找到的索引，就可以获取到要创建字典的大小:

1. @interface NSDictionary
2. ...
3. @end
5. @implementation
7. - (instancetype)initWithDictionary:(NSDictionary *)dict copyItems:(BOOL)shouldCopy {
8.   NSInteger count = dict.count;
9.   if （count >= 2^60) {
10.     // 创建的字典 key-value 对不能超过 2^60
11.     error "attempt to create a temporary id buffer which is too large or with a negative count (%lu) -- possibly data is corrupt"
12.   }
13.   
14.   NSObject *keys = nil;
15.   NSObject *objects = nil;
16.   if (count <= 0x100) {
17.     // key-value 对数量 <= 256，在栈上分配空间
18.     NSObject * keysArr[count];
19.     NSObject * objectsArr[count];
20.     keys = keysArr;
21.     objects = objectsArr;
22.   } else {
23.    // key-value 对数量 > 256，在堆上分配空间
24.    keys = _CFCreateArrayStorage(count, 0);
25.    objects = _CFCreateArrayStorage(count, 0);
26.   }
27.   
28.   // 读取参数 dict 的 keys 和 objects 到分配的数组中
29.   [dict getObjects:objects keys:keys count:count];
30.   
31.   if (count != 0 && shouldCopy) {
32.     // 拷贝 key-value 对
33.     for (NSInteger i = 0; i < count; i++) {
34.       NSObject *key = keys[i];
35.       keys[i] = NSUInteger size = __NSDictionarySizes[index];
36.     }
37.    
38.     for (NSInteger i = 0; i < count; i++) {
39.       NSObject *object = objects[i];
40.       objects[i] = [object copyWithZone:nil];
41.     }
42.   }
43.   
44.   return [self initWithObjects:objects forKeys:keys count:count];
45. }

复制代码

按照道理，直接遍历__NSDictionarySizes也能达到效果。
至于为什么要分成2个数组__NSDictionaryCapacity和__NSDictionarySizes，暂时还不清楚原因。
有了要创建字典的大小，接下来就会创建对应的__NSDictionaryI对象:

1. // -[__NSPlaceholderDictionary initWithObjects:forKeys:count]
3. @interface __NSPlaceholderDictionary
5. ...
7. @end
9. @implementation __NSPlaceholderDictionary
11. - (instancetype)initWithObjects:(ObjectType const[])objects forKeys:(ObjectTpye const[])keys count:(NSUInteger)count {
12.   if (keys == nil && count == 0) {
13.     goto label;
14.   }
15.   
16.   if (keys == nil && count != 0) {
17.     // 报错
18.     error "pointer to objects array is NULL but length is {count}";
19.   }
20.   
21.   if (keys != nil && count == 0 {
22.     goto label;
23.   }
24.   
25.   if (keys != nil && count != 0) {
26.     // 检测 keys 数组里的值是否有 nil
27.     for (NSInteger i = 0; i < count; i++) {
28.       ObjectType key = keys[i];
29.       if (key == nil) {
30.         // 报错
31.         error "attempt to insert nil object from objects{[i]}";
32.       }
33.     }
34.   }
35.   
36.   if (objects == nil && count == 0) {
37.     goto label;
38.   }
39.   
40.   if (objects == nil && count != 0) {
41.     // 报错
42.     error "pointer to objects array is NULL but length is {count}";
43.   }
44.   
45.   if (objects != nil && count == 0) {
46.     goto label;
47.   }
48.   
49.   if (objects != nil && count != 0) {
50.     // 检测 objects 数组里是否有 nil
51.     for (NSInteger i = 0; i < count; i++) {
52.       ObjectType object = objects[i];
53.       if (object == nil) {
54.         error "attempt to insert nil object from objects{[i]}";
55.       }
56.     }
57.   }
58.   
59.   label:
60.   if (self == ___immutablePlaceholderDictionary) {
61.     if (count == 0) {
62.       // 创建 __NSDictionary0
63.       return __NSDictionary0__();
64.     }
65.    
66.     if (count == 1) {
67.       // 创建 __NSSingleEntryDictionaryI
68.       return __NSSingleEntryDictionaryI_new(keys[0], objects[0], 1);
69.     }
70.    
71.     // 创建 __NSDictionaryI
72.     return __NSDictionaryI_new(keys, objects, 0, count, 1);
73.   } else if (self == ___mutablePlaceholderDictionary) {
74.     // 创建 __NSDictionaryM
75.     return __NSDictionaryM_new(keys, objecs, count, 3);
76.   }
77.   
78.   error "创建出错"
79. }

复制代码

上面代码中使用size * 8 * 2的原因是:
size代表key-value对的个数；
每一个key或者value占用8字节；
因此，一个key-value对占用16字节。
创建出的__NSDictionaryI对象，此时还没有存储任何的key-value对。
其内存布局此时为:

从内存布局可以看到，key-value对将直接存储在对象当中。
在存储key-value之前，还有一些其他属性需要存储在__NSDictionaryI对象中。

如上图所示:
第8字节的高6 bit存储这个字典对象size的索引，6 bit最多可以存储64项。
第8字节的第7 bit存储__NSDictionaryI._copyKey标志，但是现在暂时不知道它的作用。
第8字节剩余的57 bit存储实际的key-value对个数，初始值为count值。
这里有一个问题。
前面-[NSDictionary initWithDictionary:copyItems:]方法内部会对count值进行判断:

1. 0x1803cc548 <+72>:  adrp   x8, 451
2. 0x1803cc54c <+76>:  add    x8, x8, #0xc88            ; __NSDictionaryCapacities

复制代码

可以看到，count的值最多可以占用60 bit。
但是这里只使用57 bit来存储count的值，不知道是不是Apple的BUG。
设置好这些属性，接下来就要遍历keys和objects数组，通过一个栈block给__NSDictionaryI对象填充key-value对:

1. (lldb) x/64g $x8
2. 0x18058fc88: 0x0000000000000000 0x0000000000000003
3. 0x18058fc98: 0x0000000000000006 0x000000000000000b
4. 0x18058fca8: 0x0000000000000013 0x0000000000000020
5. 0x18058fcb8: 0x0000000000000034 0x0000000000000055
6. ...
7. 0x18058fe78: 0xc1d7fb9980000000 0xc2625e72e7800000

复制代码

____NSDictionaryI_new_block_invoke内部，首先对key调用hash函数获取器哈希值:

1. BOOL found = NO;
2. NSInteger index = 0;
3. for (; index < 64; index++) {
4.   if (__NSDictionaryCapacity[i] >= count) {
5.     found = YES;
6.     break;
7.   }
8. }
10. if (!found) {
11.   error "不能创建 NSDictionary";
12. }

复制代码

计算出哈希值后，对字典的size进行取余，得到的结果作为__NSDictionaryI对象中，key-value对数组的索引:

1. 0x1803cc56c <+108>: adrp   x8, 451
2. 0x1803cc570 <+112>: add    x8, x8, #0xb40            ; __NSDictionarySizes

复制代码

__NSDictionaryI对象中的key-value对数组记作__NSDictionaryI._list。
有了index索引值，就可以从__NSDictionaryI._list数组中取出对应的值:

1. (lldb) x/64g $x8
2. 0x18058fb40: 0x0000000000000000 0x0000000000000003
3. 0x18058fb50: 0x0000000000000007 0x000000000000000d
4. 0x18058fb60: 0x0000000000000017 0x0000000000000029
5. 0x18058fb70: 0x0000000000000047 0x000000000000007f
6. 0x18058fb80: 0x00000000000000bf 0x00000000000000fb
7. ...

复制代码

如果oldKey为nil，说明这个位置之前没有值，那么当前的key-value对可以安全的存储到这个位置:

需要注意的是，写入的时对 key 进行了 copy。

1. NSUInteger size = __NSDictionarySizes[index];

复制代码

因此，字典中的key必须实现copy协议。
如果oldKey不为nil，说明这个位置已经被占用了，发生了hash冲突。
这时，需要分情形处理。
如果oldKey与key是同一个对象，或者他们的isEqual方法相等:

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

复制代码

那么，当前的key-value对不会被写入，会被丢弃，同时__NSDictionaryI._used会减1。

如果oldKey与key不是同一个对象，同时，isEqual方法也不相等，那么就会从当前索引开始，遍历整个__NSDictionaryI._list数组。
如果遍历的过程中，找到了空位，那么就写入key-value对。
如果遍历的过程中，出现了上面oldKey与key相等的情形，那么就丢弃当前的key-value对，同时__NSDictionaryI._used减1。
由于字典的size总是大于或者等于count，因此不会出现遍历整个__NSDictionaryI._list数组，也找不到空位的情形。

3.4.2 内存布局

__NSDictionaryI对象完整的内存布局如下:

3.4.3 objectForKey:

-[__NSDictionaryI objectForKey:]方法首先调用参数key的hash方法:

1. BOOL found = NO;
2. NSInteger index = 0;
3. for (; index < 64; index++) {
4.   if (__NSDictionaryCapacity[i] >= count) {
5.     found = YES;
6.     break;
7.   }
8. }
10. if (!found) {
11.   error "不能创建 NSDictionary";
12. }

复制代码

和初始化过程一样，获取哈希值目的是为了得到__NSDictionaryI._list数组中的索引:

1. 0x1803cc56c <+108>: adrp   x8, 451
2. 0x1803cc570 <+112>: add    x8, x8, #0xb40            ; __NSDictionarySizes

复制代码

那此时size是如何得到的呢？
上面__NSDictionaryI对象的内存布局可以知道，size的索引存储在第8字节上。
获取到这个值，就可以从__NSDictionarySizes数组中，取得size值。
获取到index之后，就可以从__NSDictionaryI._list数组中的值:

1. NSUInteger hashValue = [key hash];

复制代码

如果candidateKey为nil，说明这个位置根本没有值，那么直接返回nil。
如果candidateKey不为nil，那么就看candidateKey与参数key是否是同一个对象，或者两者的isEqual方法相等:

1. NSUInteger index = hashValue % size;

复制代码

这种情况下，就是找到了目标key-value对，直接将对应的value值返回。
如果candidateKey与参数key既不是同一个对象，它们的isEqual方法也不相等，那么就从当前的index处开始遍历整个__NSDictionaryI._list数组。
这个过程和初始化过程有点类似:

遍历过程中，如果有candidateKey与参数key是同一个对象，或者isEqual方法相等，那么就找到了目标key-value对，直接返回value值。
如果遍历了整个数组，还是没有发现目标key-value对，就返回nil。
可以看到，如果哈希冲突比较严重，objectForKey:并不能O(1)时间返回目标值，可能需要O(size)的时间。

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