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是个环形缓冲区，必要时会动态重新分配内存空间以符合当前存储需求