NS(Mutable)Array的原理

OC数组的类体系

当我们创建一个NSArray对象时，实际上得到的是NSArray的子类__NSArrayI对象。同样的，当我们创建NSMutableArray对象时，实际上得到的是其子类__NSArrayM对象。不过，当我们创建空的或只有一个元素的NSArray对象时，得到的分别是__NSArray0或__NSSingleObjectArrayI对象。

OC数组的类体系
为什么使用NSArray和NSMutableArray，却可以得到其子类？

这个机制可以总结为以下两大步骤：
1.NSArray重写了+ (id)allocWithZone:(struct _NSZone *)zone方法。在方法内部，如果调用类为NSArray则直接返回全局变量___immutablePlaceholderArray；如果调用类为NSMutableArray则直接返回全局变量___mutablePlaceholderArray。
也就是调用[NSArray alloc]或者[NSMutableArray alloc]得到的仅仅是两个占位指针，类型为__NSPlaceholderArray。
2.在调用了alloc的基础上，不论是NSArray或NSMutableArray都必定要继续调用某个initXXX方法，而实际上调用的是__NSPlaceholderArray的initXXX。在这个initXXX方法内部，如果self == ___immutablePlaceholderArray就会重新构造并返回__NSArrayI 对象，如果self == ___mutablePlaceholderArray就会重新构造并返回_NSArrayM对象。

总结来说，对于NSArray和NSMutableArray，alloc时拿到的仅仅是个占位对象，init后才得到真实的子类对象。

上面提到了一个私有类：__NSPlaceholderArray，其内部包含有两个全局变量___immutablePlaceholderArray和___mutablePlaceholderArray。

OC数组的内部结构

NSArray和NSMutableArray，只是定义和实现了接口，而且对内部数据操作的接口都是在各个子类中实现的。所以真正需要了解的是其子类结构，了解__NSArrayI就相当于了解NSArray，了解__NSArrayM就相当于了解NSMutableArray。

1.__NSArrayI

__NSArrayI的结构定义为：

@interface __NSArrayI : NSArray {
    NSUInteger _used;
    id _list[0];
}

@end

_used是数组的元素个数
_list[0]是OC数组内部实际存储对象的数组

2.__NSSingleObjectArrayI

__NSSingleObjectArrayI的结构定义为：

@interface __NSSingleObjectArrayI : NSArray {
    id object;
}

@end

因为只有一个元素，所以只需一个object即可。

3.__NSArrayM

__NSArrayM的结构定义为：

@interface __NSArrayM : NSMutableArray {
    NSUInteger _used;
    NSUInteger _offset;
    int _size:28;
    int _unused:4;
    uint32_t _mutations;
    id *_list;
}

@end

_used是数组的元素个数
_offset实际存储对象的数组的起始偏移
_size已分配的_list大小
_mutations修改标记，每次对__NSArrayM的修改操作都会使_mutations加1
_list是个环形缓冲区，必要时会动态重新分配内存空间以符合当前存储需求

以一个初始包含5个元素，总大小_size为6的_list为例：
_offset = 0, _used = 5, _size = 6

在末端追加3个对象后：
_offset = 0, _used = 8, _size = 8
_list已重新分配

删除对象A：
_offset = 1, _used = 7, _size = 8

删除对象E：
_offset = 2, _used = 6, _size = 8
B、C往后移动了，E的空缺被填补（移动最少元素的一边）

在末端追加两个对象：
_offset = 2, _used = 8, _size = 8
_list足够存储新加入的两个对象，因此没有重新分配，而是将两个新对象存储到了_list起始端

因此可见，__NSArrayM的_list是个环形缓冲区,它的起始由_offset标识。

参考链接：
https://www.jianshu.com/p/66f8410c6bbc
https://www.sohu.com/a/235998120_208051