iOS NSArray和NSMutableArray

一、`NSArray`

iOS 在创建 NSArray 时，一般创建的是 __NSArrayI 对象，但当其只包含一个元素时，创建的是 __NSSingleObjectArrayI 对象，没有任何对象时，创建的是 __NSArray0 对象，__NSArrayI，__NSSingleObjectArrayI 和 __NSArray0 都继承自 NSArray。

1.`__NSSingleObjectArrayI`

__NSSingleObjectArrayI 的结构定义为:

@interface __NSSingleObjectArrayI : NSArray
{
    id object;
}
@end

__NSSingleObjectArrayI 类内部结构简单，只增加了一个存储对象的属性。

2.`__NSArrayI`

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

_used 是数组元素个数，调用 [array count] 返回的就是 _used 的值。
id _list[0] 是 C 语言里面的柔性数组，不占用内存，且相对指针效率更高。

二、`NSMutableArray`

iOS 创建 NSMutableArray 时，实际得到的是其子类 __NSArrayM 对象。__NSArrayM 的结构定义为

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

_list 是存储对象数组的一块连续的内存区域
_used 是数组元素个数
_offset 起始偏移量
_size 能存储的的对象个数，_list大小。（大于或等于_used)
_mutations 修改标记，每次对 __NSArrayM 的修改操作都会使 _mutations 加1,“*** Collection <__NSArrayM: 0x1002076b0> was mutated while being enumerated.”这个异常就是通过对 _mutations 的识别来引发的。

分析：__NSArrayM 并没有使用链表结果存储内存，链表虽然在增删方面有不需要移动数据的有优势，但是查找，分配，占用空间方面效率低下。在查找方面，数组可通过内存地址偏移迅速找到需要的对象，另一方面，因为内存连续，而且每个数组元素都只是一个指针，所以拷贝起来也很快。
__NSArrayM 用了环形缓冲区 (circular buffer)。这个数据结构相当简单，只是比常规数组或缓冲区复杂点。环形缓冲区的内容能在到达任意一端时绕向另一端。除非缓冲区满了，否则在任意一端插入或删除均不会要求移动任何内存。任意一端插入或者删除，只是修改 offset 参数，不需要移动内存，我们访问的时候只是不和普通的数组一样 index 多少就是多少，这里会计算加上 offset 之后处理的值取数据，而不是插入头和尾巴的时候，环形结构会根据最少移动内存指针的方式插入

例子：