最近了解了 NSMutableArray 的原理，通过这篇文章了解到了其原理，这次我就将原文的 ARM64 讨论部分省略，对 NSMutableArray 的原理进行自己的总结描述。

C语言中的数组

插入元素

删除元素

这种情况下，如果数组中的元素特别多，就会非常的耗时，那么我们使用 OC 中的 NSMutableArray 进行上述操作时，会不会也和传统的数组一样？

OC 中的NSMutableArray

NSMutableArray 与 NSArray 的差别就在 Mutable(易变的)
通过某些方法我们得到了 NSMutableArray 类的 ivars，如下

@interface __NSArrayM : NSMutableArray
{
    unsigned long long _used;
    unsigned long long _doHardRetain:1;
    unsigned long long _doWeakAccess:1;
    unsigned long long _size:62;
    unsigned long long _hasObjects:1;
    unsigned long long _hasStrongReferences:1;
    unsigned long long _offset:62;
    unsigned long long _mutations;
    id *_list;
}

我们重点关注下面四个属性

    unsigned long long _used;                     //元素的数量
    unsigned long long _size:62;                  //缓冲区的大小
    unsigned long long _offset:62;                //第一个元素在缓冲区的位置
    id *_list;                                    //指向缓冲区的指针

通过这四个属性，我们就可以实现 Mutable ，首先为了达到 Mutable 的效果，那么缓冲区的大小肯定不会是一个固定的值，当所有元素的内存占满了缓冲区后，它会以1.625倍的大小重新分配(为什么是1.625而不是2？原因) 同时，当它的大小变大后，它不会再缩小，哪怕你把其中的所有元素清除。

在大小的问题解决后，NSMutableArray 到底是如何实现添加、删除元素的？
NSMutableArray 中的数据结构为圆形缓冲区，也就是一端到底后可以从另一段开始，抽象的将原先的线性的缓冲区首尾相连。如果大家有刷算法题的话就知道这种方法在某些情况下很简单也很好用
通过上面的四个属性，我们可以自己手写出其查询方法 objectAtIndex

- (id)objectAtIndex:(NSUInteger)index
{
    if (_used <= index) {
        goto ThrowException;
    }
    
    //直接能得到的偏移量
    NSUInteger fetchOffset = _offset + index;
    //真正的偏移量
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);
    
    return _list[realOffset];
    
ThrowException:
    // exception throwing code
}

最关键的就是 fetchOffset 是否比 _size 大，如果比 _size 大 因为是圆形缓冲区，所以需要从另一段接着计算，需要查询的数据就在 fetchOffset - _size 上

我们可以通过例子来理解一下

当 fetchOffset < _size

fetchOffset < _size

假设我们需要获取 _list[3],我们只需要计算好 fetchOffset = 6，此时 realOffset = fetchOffset =6 即可得到D

当 fetchOffset > _size

fetchOffset > _size

假设我们需要获取_list[3],我们计算得到 fetchOffset = 10，如果直接使用就会导致越界，所以我们计算 realOffset = fetchOffset - _size = 0 即可得到D

很好理解，当我们需要在 NSMutableArray 的两端删除或者增加数据时，只需要修改 _size _user 和 _offset 即可，不需要对其它元素进行操作，如下图。

删除

增加

值得一提的是，它不会清理删除的指针，也就是说即使你删除了 _list[1]，但这个指针不会被删除，但是你也无法得到被你删除了的指针，因为属性的改变，你再次使用_list[1]时得到就是原先的_list[2]。

稍微复杂的情况就是在中间进行删除或者增加

删除中间元素