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），用到了环形缓冲区数据结构来处理内存移动的损耗）。

可变数组任意一端插入或删除能有固定时间的性能。而且在中间插入和删除的时候都会试着去移动最小化内存。

环形缓冲区的数据结构如果是连续数组结构，在扩容的时候难免会移动大量内存，因此用链表实现环形缓冲会更好

参考

NSMutableArray原理揭露

NSDictionary和NSMutableArray底层原理（哈希表和环形缓冲区）