NSArray是线性连续内存，这个很好理解。但是NSMutableArray是可以插入和删除的，那么如何做到高效？就比如插入，如何做到尽可能少的移动或者不移动插入元素后其他元素的内存？实现数据结构原理是什么？
NSMutableArray 和 NSArray 的基本区别
- NSMutableArray 是线程不安全的，内容可随时修改，拷贝自由
- NSArray 是线程安全的，内容无法随时修改，拷贝自由
数组的基本定义
可以归结为一段能被方便读写的连续内存空间。数组和指针并不相同，不能说：一块被 malloc 过的内存空间等同于一个数组 (一种被滥用了的说法)。
注：malloc 分配
使用一段线性内存空间的一个最明显的缺点是，在下标 0 处插入一个元素时，需要移动其它所有的元素，即 memmove 的原理：
同样地，假如想要保持相同的内存指针作为首个元素的地址，移除第一个元素需要进行相同的动作：
当数组非常大时，这样很快会成为问题。显而易见，直接指针存取在数组的世界里必定不是最高级的抽象。C 风格的数组通常很有用，但 Obj-C 程序员每天的主要工作使得它们需要 NSMutableArray 这样一个可变的、可索引的容器。
NSMutableArray
NSMutableArray 是一个类簇——其具体实现实际上是 NSMutableArray 本身的子类。
类簇是Foundation框架中广泛使用的设计模式。类簇将一些私有的、具体的子类组合在一个公共的、抽象的超类下面，以这种方法来组织类可以简化一个面向对象框架的公开架构，而又不减少功能的丰富性。
类簇 是一群隐藏在通用接口下的与实现相关的类，使得我们编写的代码可以独立于底层实现（因为接口是稳定的）。
如创建NSString对象时，你得到的可能是NSLiteralString,NSCFString,NSSimpleCString等。即不同的NSString对象调用同一个接口A，接口A的实现可能是不同的。
[NSMutableArray new] 实际上返回的是哪个类的实例呢？
答：__NSArrayM
ivars 的意思
我们来概括下每个 ivar 的意思：
- _used 是计数的意思
- _list 是缓冲区指针
- _size 是缓冲区的大小
- _offset 是在缓冲区里的数组的第一个元素索引
数据结构
__NSArrayM 用了环形缓冲区 (circular buffer)。这个数据结构相当简单，只是比常规数组或缓冲区复杂点。环形缓冲区的内容能在到达任意一端时绕向另一端。
环形缓冲区有一些非常酷的属性。尤其是，除非缓冲区满了，否则在任意一端插入或删除均不会要求移动任何内存。我们来分析这个类如何充分利用环形缓冲区来使得自身比 C 数组强大得多。在任意一端插入或者删除，只是修改offset参数，不需要移动内存，我们访问的时候只是不和普通的数组一样index多少就是多少，这里会计算加上offset之后处理的值取数据，而不是插入头和尾巴的时候，环形结构会根据最少移动内存指针的方式插入，例如要在A和B之间插入，按照C的数组，我们需要把B到E的元素移动内存，但是环形缓冲区的设计，我们只要把A的值向前移动一个单位内存，即可，同时修改offset偏移量，就能保证最小的移动单元来完成中间插入。
在两端插入或删除会相当地快，最糟糕的就是中间插入和删除中间。
子类
任何 NSMutableArray 的子类只须实现 7 个最基本的方法。所有其它高等级的抽象建立在它们的基础之上
- - count
- - objectAtIndex:
- - insertObject:atIndex:
- - removeObjectAtIndex:
- - addObject:
- - removeLastObject
- - replaceObjectAtIndex:withObject:
CFArray
当 CF 类可用时，不需要重新发明 实现了全新的 NS 类的轮子。
NSArray 或 NSMutableArray 和 CFArray 完全没有共同点。
CFArray 和 _NSArrayM 异同点
CFArray 不使用环形缓冲区，反而使用一个两端都填充着零的更大的缓冲区，使得枚举和获取正确的对象变得更加简单。在任意一端添加元素只是简单地吃到剩余的被填充的内存。
这两者有什么共同点？它们是像双向队列这类抽象数据类型的具体实现。不管它的名字，NSMutableArray 是一个类固醇数组，剥除了 C 风格数组对应的缺点。
总结
- NSMutableArray 是一个高级抽象数组，解决了 C 风格数组对应的缺点。（C数组插入的时候都会移动内存，不是O（1），用到了环形缓冲区数据结构来处理内存移动的损耗）。
- 可变数组任意一端插入或删除能有固定时间的性能。而且在中间插入和删除的时候都会试着去移动最小化内存。
- 环形缓冲区的数据结构如果是连续数组结构，在扩容的时候难免会移动大量内存，因此用链表实现环形缓冲会更好