NSMutableArray
數(shù)據(jù)結(jié)構(gòu)
- _used 計數(shù)
- _list 緩沖區(qū)指針
- _size 緩沖區(qū)大小
- _offset 緩沖區(qū)里的數(shù)組的第一個元素索引
_NSArrayM使用的底層實現(xiàn)主要是“環(huán)形緩沖區(qū)”赵誓，這個數(shù)據(jù)結(jié)構(gòu)相當(dāng)簡單温圆，只是比常規(guī)數(shù)組或緩沖區(qū)復(fù)雜一點嚷量。環(huán)形緩沖區(qū)的內(nèi)容能在到達任意一端時繞向另一端取逾。
插入/刪除
環(huán)形緩沖區(qū)在未滿的情況下插入或刪除數(shù)據(jù)，不會要求移動任何內(nèi)存箕母。在任意一端插入或者刪除储藐，只是修改offset參數(shù)俱济，不需要移動內(nèi)存。訪問數(shù)組元素的時候是通過index+offset來定位內(nèi)存地址的钙勃。插入數(shù)組中間時蛛碌，環(huán)形結(jié)構(gòu)會根據(jù)最少移動內(nèi)存的指針插入（_NSArrayM試著去最小化內(nèi)存的移動，因此會移動最少的一邊元素）辖源。
與此類似蔚携，在刪除頭部元素的時候，也只是需要修改offset克饶。在刪除中間元素時酝蜒，也只是會移動最少的一邊元素。
與C風(fēng)格數(shù)組對比
NSMutableArray是一個高級抽象數(shù)組矾湃，解決了C風(fēng)格數(shù)組對應(yīng)的缺點（C數(shù)組插入的時候都會移動內(nèi)存亡脑，不是O(1))，用到了環(huán)形緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)來處理內(nèi)存移動的損耗邀跃。而NSMutableArray在任意一端插入或刪除的時候有固定時間的性能霉咨，而在中間插入/刪除的時候都會試著去移動最小化內(nèi)存。
優(yōu)化
環(huán)形緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)如果是連續(xù)數(shù)組結(jié)構(gòu)拍屑，在擴容的時候需要移動大量內(nèi)存途戒，從這個角度看，用鏈表實現(xiàn)環(huán)形緩沖更好丽涩。
NSMutableDictionary
數(shù)據(jù)結(jié)構(gòu)
- _base
- _count
- _capacity 擴充閾值
- _bucketsNum
- _marker
- _context
- _deletes
- _xflags
- _keys
- _values
底層實現(xiàn)
NSDictionary底層其實是一個哈希表。根據(jù)數(shù)據(jù)結(jié)構(gòu)可以發(fā)現(xiàn)NSDictionary內(nèi)部使用了兩個數(shù)組分別來保存keys和values裁蚁。
NSDictionary采用連續(xù)存儲的方式存儲鍵值對矢渊，并由兩個數(shù)組分別存儲。key哈希出來數(shù)組的下標(biāo)地址枉证，同樣的這個地址對應(yīng)到values數(shù)組的下標(biāo)矮男，就是匹配到的值。因此keys和values這兩個數(shù)組的長度一致才能保證匹配到數(shù)據(jù)室谚。內(nèi)部結(jié)構(gòu)還有個_capacity表示當(dāng)前列表的擴充閾值毡鉴，當(dāng)count數(shù)量達到這個長度就擴容。
NSDictionary設(shè)置的key和value秒赤，key值會根據(jù)特定的hash函數(shù)算出建立的空桶數(shù)組猪瞬，keys和values同樣多，然后存儲數(shù)據(jù)的時候入篮，根據(jù)hash函數(shù)算出來的值陈瘦，找到對應(yīng)的index下標(biāo)。如果下標(biāo)已有數(shù)據(jù)潮售，開放定址法后移動插入痊项。如果空桶數(shù)組的數(shù)量達到數(shù)據(jù)閾值锅风，這個時候就把空桶數(shù)組擴容，然后重新哈希插入鞍泉。
這樣把一些不連續(xù)的key-value值插入到能建立起關(guān)系的hash表中皱埠，當(dāng)我們查找的時候，key根據(jù)哈希值算出來咖驮，然后根據(jù)索引边器，直接index訪問hash表的hash和values，這樣查詢速度就可以和連續(xù)線性存儲的數(shù)據(jù)一樣接近O(1)了游沿，只是占用空間有點大饰抒。刪除的時候，根據(jù)marker標(biāo)記邏輯上的刪除诀黍，除非NSDictionary內(nèi)存被移除袋坑。
