最近了解了 NSMutableArray 的原理，通過這篇文章了解到了其原理骄崩，這次我就將原文的 ARM64 討論部分省略辛友，對 NSMutableArray 的原理進(jìn)行自己的總結(jié)描述叉谜。

C語言中的數(shù)組

插入元素

刪除元素

這種情況下认轨，如果數(shù)組中的元素特別多，就會非常的耗時月培，那么我們使用 OC 中的 NSMutableArray 進(jìn)行上述操作時嘁字，會不會也和傳統(tǒng)的數(shù)組一樣？

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;
}

我們重點關(guān)注下面四個屬性

    unsigned long long _used;                     //元素的數(shù)量
    unsigned long long _size:62;                  //緩沖區(qū)的大小
    unsigned long long _offset:62;                //第一個元素在緩沖區(qū)的位置
    id *_list;                                    //指向緩沖區(qū)的指針

通過這四個屬性纪蜒，我們就可以實現(xiàn) Mutable ，首先為了達(dá)到 Mutable 的效果此叠，那么緩沖區(qū)的大小肯定不會是一個固定的值纯续，當(dāng)所有元素的內(nèi)存占滿了緩沖區(qū)后，它會以1.625倍的大小重新分配(為什么是1.625而不是2灭袁？原因) 同時猬错，當(dāng)它的大小變大后，它不會再縮小简卧，哪怕你把其中的所有元素清除兔魂。

在大小的問題解決后，NSMutableArray 到底是如何實現(xiàn)添加举娩、刪除元素的析校？
NSMutableArray 中的數(shù)據(jù)結(jié)構(gòu)為圓形緩沖區(qū)，也就是一端到底后可以從另一段開始铜涉，抽象的將原先的線性的緩沖區(qū)首尾相連智玻。如果大家有刷算法題的話就知道這種方法在某些情況下很簡單也很好用
通過上面的四個屬性，我們可以自己手寫出其查詢方法 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
}

最關(guān)鍵的就是 fetchOffset 是否比 _size 大芙代，如果比 _size 大 因為是圓形緩沖區(qū)吊奢，所以需要從另一段接著計算，需要查詢的數(shù)據(jù)就在 fetchOffset - _size 上

我們可以通過例子來理解一下

當(dāng) fetchOffset < _size

fetchOffset < _size

假設(shè)我們需要獲取 _list[3],我們只需要計算好 fetchOffset = 6纹烹，此時 realOffset = fetchOffset =6 即可得到D

當(dāng) fetchOffset > _size

fetchOffset > _size

假設(shè)我們需要獲取_list[3],我們計算得到 fetchOffset = 10页滚，如果直接使用就會導(dǎo)致越界召边，所以我們計算 realOffset = fetchOffset - _size = 0 即可得到D

很好理解，當(dāng)我們需要在 NSMutableArray 的兩端刪除或者增加數(shù)據(jù)時裹驰，只需要修改 _size _user 和 _offset 即可隧熙，不需要對其它元素進(jìn)行操作，如下圖幻林。

刪除

增加

值得一提的是贞盯，它不會清理刪除的指針，也就是說即使你刪除了 _list[1]沪饺，但這個指針不會被刪除躏敢，但是你也無法得到被你刪除了的指針，因為屬性的改變整葡，你再次使用_list[1]時得到就是原先的_list[2]件余。

稍微復(fù)雜的情況就是在中間進(jìn)行刪除或者增加

刪除中間元素