探索iOS数组容器的存储结构

在C++中我们我们通常使用顺序存储作为数组的存储结构, 那在OC中, 封装过的NSArray和NSMutableArray到底是顺序存储还是链式存储的呢, 今天就来一探究竟.

上代码

    NSString *str = @"11";
    NSLog(@"%p", str);
    NSArray *array = @[str, @"1", @"2"];
    NSLog(@"array:%p", array);

这里用NSArray数组存放3个元素, 第一个元素是@"11"这个字符串, 我们知道, 字符串是作为常量的, 地址是不会改变的, 并且, 数组的首地址就是str的地址, 因此我们打印出str的地址.

控制台输出如下

0x104f5d078

然后我们在NSLog(@"array:%p", array);这一行下断点, 并打印当前的内存情况

命令 (lldb) x/100xb array

控制台输出如下

0x60000024b1c0: 0xc0 0xda 0x1c 0x06 0x01 0x00 0x00 0x00
0x60000024b1c8: 0x03 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b1d0: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b1d8: 0x04 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b1e0: 0xe0 0x94 0x22 0x00 0x00 0x60 0x00 0x00
0x60000024b1e8: 0x60 0xad 0x03 0x00 0x00 0x60 0x00 0x00
0x60000024b1f0: 0xad 0xbe 0xb7 0x66 0x89 0xf7 0xdd 0xba
0x60000024b1f8: 0x80 0xaf 0x24 0x00 0x00 0x60 0x00 0x00
0x60000024b200: 0xc0 0x79 0x22 0x00 0x00 0x60 0x00 0x00
0x60000024b208: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b210: 0x61 0x63 0x74 0x69 0x6f 0x6e 0x00 0x00
0x60000024b218: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b220: 0xd0 0xb0 0x24 0x00

这里的内存主要打印的是NSArray这个"结构体"(所有的OC对象实际都是结构体)在内存上的存储情况.

0x60000024b1c8: 0x03 0x00 0x00 0x00 0x00 0x00 0x00 0x00

这一行0x03我们猜想是数组的长度, 感兴趣的小伙伴可以换下数组, 发现这里确实是数组的长度, 那数组里面的真实的数据在哪里呢?
首先这些真实数据的首地址一定在NSArray这个"结构体"里面有存储, 也就是x/100xb array对应的控制台输出一定有一行表示这个地址.由于从左往右是从低到高, 看下哪些可能像地址, 目标定位到0x60000024b1e0和0x60000024b1e8这两行, 先打印0x60000024b1e0的内存

命令 (lldb) x/100xb 0x6000002294e0

控制台输出如下

0x6000002294e0: 0x78 0xd0 0xf5 0x04 0x01 0x00 0x00 0x00
0x6000002294e8: 0xb8 0xd0 0xf5 0x04 0x01 0x00 0x00 0x00
0x6000002294f0: 0xd8 0xd0 0xf5 0x04 0x01 0x00 0x00 0x00
0x6000002294f8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000229500: 0xad 0xbe 0xb7 0x66 0x89 0xf7 0xdd 0xba
0x600000229508: 0xc0 0x93 0x22 0x00 0x00 0x60 0x00 0x00
0x600000229510: 0x0c 0x53 0x77 0x69 0x73 0x73 0x20 0x47
0x600000229518: 0x65 0x72 0x6d 0x61 0x6e 0x00 0x00 0x00
0x600000229520: 0x18 0xe2 0x1c 0x06 0x01 0x00 0x00 0x00
0x600000229528: 0x8c 0x07 0x00 0x00 0x01 0x00 0x00 0x00
0x600000229530: 0x0c 0x47 0x72 0x6f 0x75 0x70 0x2d 0x4e
0x600000229538: 0x6f 0x72 0x64 0x69 0x63 0x00 0x00 0x00
0x600000229540: 0x18 0xe2 0x1c 0x06

看这里的第一行内存里的数据是0x0104f5d078, 这个数据刚好就是str的地址, 因此我们先假0x6000002294e0就是数组对应的真实数据的首地址, 然后分别打印这些对象的真实数据

命令 (lldb)po 0x0104f5d078
11
(lldb) po 0x0104f5d0b8
1
(lldb) po 0x0104f5d0d8
2
真的是数组里面的数据, 再看下存储这些对象的内存地址

0x6000002294e0
0x6000002294e8
0x6000002294f0

刚好都差8个字节, 我们知道OC里面的数组存储的是对象类型, 也就是指针, 指针在64位系统上是8个字节, 这就印证了我们的一个假设NSArray在内存上是连续存储的.
为了进一步研究, 我们打印刚才NSArray"结构体"中另一个可疑的首地址的内存情况0x60000024b1e8

(lldb) x/100xb 0x60000024b1e8
0x60000024b1e8: 0x60 0xad 0x03 0x00 0x00 0x60 0x00 0x00
0x60000024b1f0: 0xad 0xbe 0xb7 0x66 0x89 0xf7 0xdd 0xba
0x60000024b1f8: 0x80 0xaf 0x24 0x00 0x00 0x60 0x00 0x00
0x60000024b200: 0xc0 0x79 0x22 0x00 0x00 0x60 0x00 0x00
0x60000024b208: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b210: 0x61 0x63 0x74 0x69 0x6f 0x6e 0x00 0x00
0x60000024b218: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60000024b220: 0xd0 0xb0 0x24 0x00 0x00 0x60 0x00 0x00
0x60000024b228: 0x20 0xbe 0x23 0x00 0x80 0x60 0x00 0x00
0x60000024b230: 0x55 0xe6 0xf6 0x55 0x35 0x05 0x00 0xa0
0x60000024b238: 0x40 0xd7 0x09 0x00 0x00 0x60 0x00 0x00
0x60000024b240: 0xa0 0x0a 0x28 0x00 0x80 0x60 0x00 0x00
0x60000024b248: 0xf0 0x0a 0x28 0x00

尝试打印里面的数据

(lldb) po 0x60000003ad60
105553116507488

0x60000003ad60好像做不起首地址.

下面研究下NSMutableArray的存储情况, 根据NSArray是顺序存储这个事实, 我们假设NSMutableArray也是顺序存储的. 大胆假设还需小心求证.

上代码

    NSString *str = @"11";
    NSLog(@"%p", str);
    NSMutableArray *arrayM = [NSMutableArray array];
    for (int i = 0; i < 10; i++) {
        [arrayM addObject:str];
    }
    NSLog(@"arrayM:%p", arrayM);

这里NSMutableArray和NSArray不同的地方就是NSMutableArray可能需要扩容

看初始化的内存情况

(lldb) x/100xb arrayM
0x600000278b40: 0x98 0x3a 0xde 0x04 0x01 0x00 0x00 0x00
0x600000278b48: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b50: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b58: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b60: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b68: 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b70: 0x40 0x38 0x22 0x00 0x00 0x60 0x00 0x00
0x600000278b78: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b80: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x600000278b88: 0x80 0x84 0x27 0x00 0x00 0x60 0x00 0x00
0x600000278b90: 0x80 0xf0 0x25 0x00 0x00 0x60 0x00 0x00
0x600000278b98: 0x00 0x00 0x00 0x00 0x73 0x42 0x61 0x72
0x600000278ba0: 0x70 0x72 0x6f 0x63

0x40 0x38 0x22 0x00 0x00 0x60 可能存的是首地址吧, who care, 执行完一次[arrayM addObject:str];后的内存

(lldb) x/100xb arrayM
0x600000278b40: 0x98 0x3a 0xde 0x04 0x01 0x00 0x00 0x00
0x600000278b48: 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b50: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b58: 0x02 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b60: 0xa0 0xaa 0x01 0x00 0x80 0x60 0x00 0x00
0x600000278b68: 0x02 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b70: 0x40 0x38 0x22 0x00 0x00 0x60 0x00 0x00
0x600000278b78: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b80: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x600000278b88: 0x80 0x84 0x27 0x00 0x00 0x60 0x00 0x00
0x600000278b90: 0x80 0xf0 0x25 0x00 0x00 0x60 0x00 0x00
0x600000278b98: 0x00 0x00 0x00 0x00 0x73 0x42 0x61 0x72
0x600000278ba0: 0x70 0x72 0x6f 0x63

继续看可疑的首地址

(lldb) x/100xb 0x60800001aaa0
0x60800001aaa0: 0x78 0xb0 0x69 0x03 0x01 0x00 0x00 0x00
0x60800001aaa8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60800001aab0: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x60800001aab8: 0x70 0xaa 0x01 0x00 0x80 0x60 0x00 0x00
0x60800001aac0: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x60800001aac8: 0xa0 0xab 0x01 0x00 0x80 0x60 0x00 0x00
0x60800001aad0: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x60800001aad8: 0x10 0xaa 0x01 0x00 0x80 0x60 0x00 0x00
0x60800001aae0: 0x00 0xaa 0x81 0x41 0xe2 0x7f 0x00 0x00
0x60800001aae8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x60800001aaf0: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x60800001aaf8: 0xb0 0xaa 0x01 0x00 0x80 0x60 0x00 0x00
0x60800001ab00: 0xd8 0x45 0xde 0x04
(lldb) po 0x010369b078
11

果然11进来了
再看执行了2次add后的内存

(lldb) x/100xb arrayM
0x600000278b40: 0x98 0x3a 0xde 0x04 0x01 0x00 0x00 0x00
0x600000278b48: 0x04 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b50: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b58: 0x04 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b60: 0x20 0x38 0x22 0x00 0x00 0x60 0x00 0x00
0x600000278b68: 0x05 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b70: 0x40 0x38 0x22 0x00 0x00 0x60 0x00 0x00
0x600000278b78: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000278b80: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x600000278b88: 0x80 0x84 0x27 0x00 0x00 0x60 0x00 0x00
0x600000278b90: 0x80 0xf0 0x25 0x00 0x00 0x60 0x00 0x00
0x600000278b98: 0x00 0x00 0x00 0x00 0x73 0x42 0x61 0x72
0x600000278ba0: 0x70 0x72 0x6f 0x63

首地址变成了0x20 0x38 0x22 0x00 0x00 0x60, 这是由于扩容导致的

(lldb) x/100xb 0x600000223820
0x600000223820: 0x78 0xb0 0x69 0x03 0x01 0x00 0x00 0x00
0x600000223828: 0x78 0xb0 0x69 0x03 0x01 0x00 0x00 0x00
0x600000223830: 0x78 0xb0 0x69 0x03 0x01 0x00 0x00 0x00
0x600000223838: 0x78 0xb0 0x69 0x03 0x01 0x00 0x00 0x00
0x600000223840: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000223848: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000223850: 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000223858: 0xa8 0x70 0xde 0x04 0x01 0x00 0x00 0x00
0x600000223860: 0xad 0xbe 0x4c 0xac 0xb5 0x25 0xdd 0xba
0x600000223868: 0xa0 0x3a 0x22 0x00 0x00 0x60 0x00 0x00
0x600000223870: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000223878: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x600000223880: 0xb0 0xed 0x25 0x00

还是顺序存储的. 有兴趣的小伙伴可以继续看下执行完10次add后的情况, 结论是:还是顺序存储的, 不过首地址会经常变.

综上NSArray和NSMutableArray在内存上都是顺序存储的, 这可能和我之前想的NSMutableArray是链式存储的说法有些出入, 要深入研究才能知道真实情况和我们想的有什么区别. 精通iOS, 从lldb开始.